Computing the similarity of two strings or sequences is one of the most important fundamental in computer field, and it has been widely studied for several decades. In the last decade, it gained the researchers' attentions again because of the improvements of the hardware computation ability and the presence of huge amount of data in biotechnology. In this dissertation, we pay attention to computing the edit distance between two sequences where the block-edit operations are involved in addition to the character-edit operations. Previous researches show that this problem is NP-hard if recursive block moves are allowed. Since we are interested in solving the editing problems by the polynomial-time optimization algorithms, we consider the simplified version of the edit distance problem. We first focus on the longest common subsequence (LCS) of run-length encoded (RLE) strings, where the runs can be seen as a class of simplified blocks. Then, we apply constraints to the problem, i.e. to find the constrained LCS (CLCS) of RLE strings. Besides, we show that the problems which involve block-edit operations can still be solved by the polynomial-time optimization algorithms if some restrictions are applied. Let X and Y be two sequences of lengths n and m, respectively. Also, let N and M, be the numbers of runs in the corresponding RLE forms of X and Y, respectively. In this dissertation, first, we propose a simple algorithm for computing the LCS of X and Y in O(NM + min{ p_1, p_2 }) time, where p_1 and p_2 denote the numbers of elements in the bottom and right boundaries of the matched blocks, respectively. This new algorithm improves the previously known time bound O(min{nM, Nm}) and outperforms the time bounds O(NM log NM) or O((N+M+q) log (N+M+q)) for some cases, where q denotes the number of matched blocks. Next, we give an efficient algorithm for solving the CLCS problem, which is to find a common subsequences Z of X and Y such that a given constrained sequence P is a subsequence of Z and the length of Z is maximized. Suppose X, Y and P are all in RLE format, and the lengths of X, Y and P are n, m and r, respectively. Let N, M and R be the numbers of runs in X, Y, and P, respectively. We show that by RLE, the CLCS problem can be solved in O(NMr + min{q_1 r + q_4, q_2 r + q_5 }) time, where q_1 and q_2 denote the numbers of elements in the south and east boundaries of the partially matched blocks on the first layer, respectively, and q_4 and q_5 denote the numbers of elements of the west and north pillars in the bottom boundaries of all fully matched cuboids in the DP lattice, respectively. When the input strings have good compression ratios, our work obviously outperforms the previously known DP algorithms and the Hunt-Szymanski-like algorithms. Finally, we consider variations of the block edit distance problem that involve character insertions, character deletions, block copies and block deletions, for two given sequences X and Y. In this dissertation, three variations are defined with different measuring functions, which are P(EIS, C), P(EI, L) and P(EI, N). Then we show that with some preprocessing, the minimum block edit distances of these three variations can be obtained by dynamic programming in O(nm), O(nm log m) and O(nm^2) time, respectively, where n and m are the lengths of X and Y.

Even a modest positive autocorrelation results in a considerable increase in the number of false alarms that are produced when applying a CUSUM chart. Knowledge of the process to be controlled allows for suitable adaptation of the CUSUM procedure. If one has to suspect the normality assumption, nonparametric control procedures such as the rank-based CUSUM chart are a practical alternative. The paper reports the results of a simulation study on the robustness (in terms of sensitivity of the ARL) of the rank-based CUSUM chart against serial correlation of the control variable. The results indicate that the rank-based CUSUM chart is less affected by correlation than the observation-based chart: The rank-based CUSUM chart shows a smaller increase in the number of false alarms and a higher decrease in the ARL in the out-of-control case than the the observation-based chart. (author's abstract) / Series: Forschungsberichte / Institut für Statistik

Computer-generated imagery is ubiquitous in today's society, appearing in advertisements, video games, and computer-animated movies among other places. Much of this imagery needs to be as realistic as possible, and animators have turned to techniques such as fluid simulation to create scenes involving substances like smoke, fire, and water. The Lattice-Boltzmann Method (LBM) is one fluid simulation technique that has gained recent popularity due to its relatively simple basic algorithm and the ease with which it can be distributed across multiple processors. Unfortunately, current LBM simulations also suffer from high memory usage and restrict free surface fluids to domains of fixed size. This thesis modifies the LBM to utilize a recursive run-length-encoded (RLE) grid data structure instead of the standard fixed array of grid cells, which reduces the amount of memory required for LBM simulations as well as allowing the domain to grow and shrink as necessary to accomodate a liquid surface. The modified LBM is implemented within the open-source 3D animation package Blender and compared to Blender's current LBM simulator using the metrics of memory usage and time required to complete a given simulation. Results show that, although the RLE-based simulator can take several times longer than the current simulator to complete a given simulation, the memory usage is significantly reduced, making an RLE-based simulation preferable in a few specific circumstances.

Low back pain is one of the most common and disabling musculoskeletal disorders worldwide and the third most common reason for surgery in the United States. The lower back, or lumbar region, supports most of the body's weight; it controls spinal movement and stability through the interaction between bones, nerves, muscles, ligaments, and fascia within the lumbar region. Any disorder of those tissues could cause low back pain (LBP); emerging evidence indicates that the thoracolumbar fascia (TLF) is the lower back's most pain-sensitive soft tissue structure. TLF consists of dense connective tissue separated by loose connective tissue, allowing TLF layers to pass easily during torso movement. A series of foundational studies found that patients enduring long-term low back pain have different TLF structures than those without LBP. Injuries may result in adhesions and fibrosis, which may cause adjacent dense connective tissue layers to lose independent motion, limiting movement and causing pain. LBP is diagnosed by investigating the patient's medical history to identify symptoms and then examining the patient to determine the cause of the pain. If the pain persists after diagnosis and treatment, further investigation is required; an ultrasound scan is used as the next step. Ultrasound (US) imaging is a non-invasive and instantaneous method to evaluate soft, connective tissue structures such as muscles, tendons, ligaments, and fascia. Even though measuring echo intensity helps evaluate the soft tissues, this method still has limitations in diagnosing LBP; 90 % of all LBP patients are diagnosed with non-specific LBP, referred to as pain with no definitive cause . An in-depth investigation of US images could potentially provide more specificity in identifying sources of LBP. By providing information about soft tissue structure, texture analysis could increase US images' diagnostic power. The texture of an ultrasound image is the variation of pixel intensities throughout the region of interest (ROI) that produces different patterns; texture analysis is an approach that quantifies the characteristic variation of pixel intensities within ROI to describe tissue morphological characteristics. First-order texture analysis, second-order texture analysis, and grey-level run length texture analysis are types of analysis that could be applied to quantify parameters that describe the features of the texture; the grey-level analysis is usually conducted in four directions of the texture. This study has four objectives; the first objective is to use first-order and second-order analysis to determine texture parameters and determine whether those parameters can differentiate between individuals with and without LBP. The second objective is to use grey level run length analysis to quantify texture parameters in four directions (0^°,45^°,90^°,135^°) and examine whether those parameters can differentiate between individuals with and without LBP. The third objective is to determine the correlation between the first, second, and run length parameters. The fourth objective is to explore how first-order, second order and grey level run length parameters are affected by US machine settings. A custom-written MATLAB program was developed to quantify first and second-order texture parameters and grey-level run length parameters. Using JMP software, each parameter was statistically compared between individuals with and without LBP. Among nine first- and second-order texture parameters, four showed statistically significant differences between individuals with and without LBP. Among 44 run-length parameters, 9 showed statistically significant differences between individuals with and without LBP. The current study also revealed some strong correlations between first, second, and run length parameters; it also shows that the US machine setting has minor effects on the three types of parameters. Although the present study was conducted on a relatively small sample size, the results indicate that one direction of grey level run length analysis and first and second-order texture analysis can differentiate between people with and without LBP. / Master of Science / Low back pain (LBP) is one of the most common and disabling musculoskeletal disorders worldwide and the third most common reason for surgery in the United States. Due to LBP's effect on mobility, it is one of the leading causes of absence from work, early retirement, and long-term disability payments. The thoracolumbar fascia (TLF), a connective tissue that stabilizes the trunk, pelvis, and spine, is considered the most sensitive tissue to LBP. LBP diagnosis is based on the patient's medical history to identify symptoms and then on an examination to determine the cause. If the pain persists after diagnosis and treatment, imaging is recommended as the next step. Ultrasound (US) imaging produces a cross-sectional image of the structure and has been used to compare TLF structure in people with and without LBP. Additional analyses must be done to increase US images' ability to diagnose LBP. In the current project, three types of analysis of US images were performed; first-order, second-order, and grey level run length analyses were performed to determine parameters for the images of the two groups of people; selected parameters were noted to distinguish between people with and without LBP.

As time passes, change occurs. With this change comes the need for surveillance. One may be a technician on an assembly line and in need of a surveillance technique to monitor the number of defective components produced. On the other hand, one may be an administrator of a hospital in need of surveillance measures to monitor the number of patient falls in the hospital or to monitor surgical outcomes to detect changes in surgical failure rates. A natural choice for on-going surveillance is the control chart; however, the chart must be constructed in a way that accommodates the situation at hand. Two scenarios involving attribute control charting are investigated here. The first scenario involves Poisson count data where the area of opportunity changes. A modified exponentially weighted moving average (EWMA) chart is proposed to accommodate the varying sample sizes. The performance of this method is compared with the performance for several competing control chart techniques and recommendations are made regarding the best preforming control chart method. This research is a result of joint work with Dr. William H. Woodall (Department of Statistics, Virginia Tech). The second scenario involves monitoring a process where items are classified into more than two categories and the results for these classifications are readily available. A multinomial cumulative sum (CUSUM) chart is proposed to monitor these types of situations. The multinomial CUSUM chart is evaluated through comparisons of performance with competing control chart methods. This research is a result of joint work with Mr. Lee J. Wells (Grado Department of Industrial and Systems Engineering, Virginia Tech) and Dr. William H. Woodall (Department of Statistics, Virginia Tech). / Ph. D.

[pt] A modelagem de reservatórios consiste em uma tarefa de muita relevância na medida em que permite a representação de uma dada região geológica de interesse. Dada a incerteza envolvida no processo, deseja-se gerar uma grande quantidade de cenários possíveis para se determinar aquele que melhor representa essa região. Há, então, uma forte demanda de se gerar rapidamente cada simulação. Desde a sua origem, diversas metodologias foram propostas para esse propósito e, nas últimas duas décadas, Multiple-Point Geostatistics (MPS) passou a ser a dominante. Essa metodologia é fortemente baseada no conceito de imagem de treinamento (TI) e no uso de suas características, que são denominadas de padrões. No presente trabalho, é proposto um novo método de MPS que combina a aplicação de dois conceitos-chave: a técnica denominada Locality Sensitive Hashing (LSH), que permite a aceleração da busca por padrões similares a um dado objetivo; e a técnica de compressão Run-Length Encoding (RLE), utilizada para acelerar o cálculo da similaridade de Hamming. Foram realizados experimentos com imagens de treinamento tanto categóricas quanto contínuas que evidenciaram que o LSHSIM é computacionalmente eficiente e produz realizações de boa qualidade, enquanto gera um espaço de incerteza de tamanho razoável. Em particular, para dados categóricos, os resultados sugerem que o LSHSIM é mais rápido do que o MS-CCSIM, que corresponde a um dos métodos componentes do estado-da-arte. / [en] Reservoir modeling is a very important task that permits the representation of a geological region of interest. Given the uncertainty involved in the process, one wants to generate a considerable number of possible scenarios so as to find those which best represent this region. Then, there is a strong demand for quickly generating each simulation. Since its inception, many methodologies have been proposed for this purpose and, in the last two decades, multiple-point geostatistics (MPS) has been the dominant one. This methodology is strongly based on the concept of training image (TI) and the use of its characteristics, which are called patterns. In this work, we propose a new MPS method that combines the application of a technique called Locality Sensitive Hashing (LSH), which permits to accelerate the search for patterns similar to a target one, with a Run-Length Encoding (RLE) compression technique that speeds up the calculation of the Hamming similarity. We have performed experiments with both categorical and continuous images which showed that LSHSIM is computationally efficient and produce good quality realizations, while achieving a reasonable space of uncertainty. In particular, for categorical data, the results suggest that LSHSIM is faster than MS-CCSIM, one of the state-of-the-art methods.

Statistical Process Control (SPC), and in particular control charting, is widely used to achieve and maintain control of various processes in manufacturing. A control chart is a graphical display that plots quality characteristics versus the sample number or the time line. Interest in effective implementation of control charts for autocorrelated processes has increased in recent years. However, because of the complexities involved, few systematic design approaches have thus far been developed. Many control charting methods can be viewed as the charting of the output of a linear filter applied to the process data. In this dissertation, we generalize the concept of linear filters for control charts and propose new control charting schemes, the general linear filter (GLF) and the 2nd-order linear filter, based on the generalization. In addition, their optimal design methodologies are developed, where the filter parameters are optimally selected to minimize the out-of-control Average Run Length (ARL) while constraining the in-control ARL to some desired value. The optimal linear filters are compared with other methods in terms of ARL performance, and a number of their interesting characteristics are discussed for various types of mean shifts (step, spike, sinusoidal) and various ARMA process models (i.i.d., AR(1), ARMA(1,1)). Also, in this work, a new discretization approach for substantially reducing the computational time and memory use for the Markov chain method of calculating the ARL is proposed. Finally, a gradient-based optimization strategy for searching optimal linear filters is illustrated.

O presente trabalho propõe um método para a aplicação do gráfico de controle de regressão para o monitoramento de processos industriais. O método proposto inclui uma modificação do gráfico de controle de regressão múltipla, permitindo o monitoramento direto da característica de qualidade do processo ao invés do monitoramento dos resíduos padronizados do modelo de regressão, facilitando a interpretação dos operadores do processo. O método é dividido em duas fases principais: (i) Fase I - análise retrospectiva e (ii) Fase II - monitoramento do processo. A Fase I é composta pela coleta das amostras iniciais, estimação do modelo de regressão e análise de estabilidade dos dados coletados e, a partir desta fase, define-se alguns parâmetros a serem utilizados na fase seguinte. A Fase II do método consiste na coleta periódica de amostras, verificação da extrapolação dos valores das variáveis de controle e monitoramento do processo propriamente dito. O método proposto foi validado através da aplicação em um processo produtivo e de uma comparação do número médio de amostras (NMA) do gráfico de controle de regressão proposto, gerado através de simulação de Monte Carlo, com outros procedimentos similares encontrados na literatura. Como principais resultados esta dissertação apresenta: (i) proposta de um método sistematizado para nortear a aplicação de gráficos de controle de regressão; (ii) adaptação do gráfico de controle de regressão, de forma a permitir o monitoramento direto da característica de qualidade; (iii) proposta de um procedimento gráfico para a verificação da extrapolação das variáveis de controle e (iv) obtenção do NMA do gráfico de controle de regressão proposto e de outros procedimentos encontrados na literatura. O método proposto foi aplicado em um processo produtivo de uma indústria de borrachas. / This work proposes a method for the application of regression control charts in the monitoring of industrial processes. In order to facilitate the interpretation by the process operators, a modification in the multiple regression control chart is proposed allowing the direct monitoring of the values of quality characteristic of the process, instead of monitoring the regression standardized residuals. The proposed method is divided into two Phases: (i) Phase I, called retrospective analysis, and Phase II, called process monitoring. Phase I is composed by sampling, estimation of linear regression model and verification of stability of these samples. This phase defines some parameters to be used in the following phase. Phase II consists in periodic sampling of the process, altogether with verification of the extrapolation of process control variables and the process monitoring itself. The proposed method was validated through practical application in an industrial process and compared with other procedures found in literature. This work has also achieved the average run length (ARL) of the proposed regression control chart, which was compared with the other procedures consulted. The main contributions of this work may be pointed: (i) the proposal of a method to guide the application of regression control chart; (ii) the adaptation of the multiple regression control chart, allowing the direct monitoring of the quality characteristic; (iii) the proposal of a control chart to monitor the extrapolation of the process control variable and (iv) the obtaining of the ARL of the proposed regression control chart and other similar procedures. The proposed method was applied in a process of a rubber manufactory.

O presente trabalho propõe um método para a aplicação do gráfico de controle de regressão para o monitoramento de processos industriais. O método proposto inclui uma modificação do gráfico de controle de regressão múltipla, permitindo o monitoramento direto da característica de qualidade do processo ao invés do monitoramento dos resíduos padronizados do modelo de regressão, facilitando a interpretação dos operadores do processo. O método é dividido em duas fases principais: (i) Fase I - análise retrospectiva e (ii) Fase II - monitoramento do processo. A Fase I é composta pela coleta das amostras iniciais, estimação do modelo de regressão e análise de estabilidade dos dados coletados e, a partir desta fase, define-se alguns parâmetros a serem utilizados na fase seguinte. A Fase II do método consiste na coleta periódica de amostras, verificação da extrapolação dos valores das variáveis de controle e monitoramento do processo propriamente dito. O método proposto foi validado através da aplicação em um processo produtivo e de uma comparação do número médio de amostras (NMA) do gráfico de controle de regressão proposto, gerado através de simulação de Monte Carlo, com outros procedimentos similares encontrados na literatura. Como principais resultados esta dissertação apresenta: (i) proposta de um método sistematizado para nortear a aplicação de gráficos de controle de regressão; (ii) adaptação do gráfico de controle de regressão, de forma a permitir o monitoramento direto da característica de qualidade; (iii) proposta de um procedimento gráfico para a verificação da extrapolação das variáveis de controle e (iv) obtenção do NMA do gráfico de controle de regressão proposto e de outros procedimentos encontrados na literatura. O método proposto foi aplicado em um processo produtivo de uma indústria de borrachas. / This work proposes a method for the application of regression control charts in the monitoring of industrial processes. In order to facilitate the interpretation by the process operators, a modification in the multiple regression control chart is proposed allowing the direct monitoring of the values of quality characteristic of the process, instead of monitoring the regression standardized residuals. The proposed method is divided into two Phases: (i) Phase I, called retrospective analysis, and Phase II, called process monitoring. Phase I is composed by sampling, estimation of linear regression model and verification of stability of these samples. This phase defines some parameters to be used in the following phase. Phase II consists in periodic sampling of the process, altogether with verification of the extrapolation of process control variables and the process monitoring itself. The proposed method was validated through practical application in an industrial process and compared with other procedures found in literature. This work has also achieved the average run length (ARL) of the proposed regression control chart, which was compared with the other procedures consulted. The main contributions of this work may be pointed: (i) the proposal of a method to guide the application of regression control chart; (ii) the adaptation of the multiple regression control chart, allowing the direct monitoring of the quality characteristic; (iii) the proposal of a control chart to monitor the extrapolation of the process control variable and (iv) the obtaining of the ARL of the proposed regression control chart and other similar procedures. The proposed method was applied in a process of a rubber manufactory.

O presente trabalho propõe um método para a aplicação do gráfico de controle de regressão para o monitoramento de processos industriais. O método proposto inclui uma modificação do gráfico de controle de regressão múltipla, permitindo o monitoramento direto da característica de qualidade do processo ao invés do monitoramento dos resíduos padronizados do modelo de regressão, facilitando a interpretação dos operadores do processo. O método é dividido em duas fases principais: (i) Fase I - análise retrospectiva e (ii) Fase II - monitoramento do processo. A Fase I é composta pela coleta das amostras iniciais, estimação do modelo de regressão e análise de estabilidade dos dados coletados e, a partir desta fase, define-se alguns parâmetros a serem utilizados na fase seguinte. A Fase II do método consiste na coleta periódica de amostras, verificação da extrapolação dos valores das variáveis de controle e monitoramento do processo propriamente dito. O método proposto foi validado através da aplicação em um processo produtivo e de uma comparação do número médio de amostras (NMA) do gráfico de controle de regressão proposto, gerado através de simulação de Monte Carlo, com outros procedimentos similares encontrados na literatura. Como principais resultados esta dissertação apresenta: (i) proposta de um método sistematizado para nortear a aplicação de gráficos de controle de regressão; (ii) adaptação do gráfico de controle de regressão, de forma a permitir o monitoramento direto da característica de qualidade; (iii) proposta de um procedimento gráfico para a verificação da extrapolação das variáveis de controle e (iv) obtenção do NMA do gráfico de controle de regressão proposto e de outros procedimentos encontrados na literatura. O método proposto foi aplicado em um processo produtivo de uma indústria de borrachas. / This work proposes a method for the application of regression control charts in the monitoring of industrial processes. In order to facilitate the interpretation by the process operators, a modification in the multiple regression control chart is proposed allowing the direct monitoring of the values of quality characteristic of the process, instead of monitoring the regression standardized residuals. The proposed method is divided into two Phases: (i) Phase I, called retrospective analysis, and Phase II, called process monitoring. Phase I is composed by sampling, estimation of linear regression model and verification of stability of these samples. This phase defines some parameters to be used in the following phase. Phase II consists in periodic sampling of the process, altogether with verification of the extrapolation of process control variables and the process monitoring itself. The proposed method was validated through practical application in an industrial process and compared with other procedures found in literature. This work has also achieved the average run length (ARL) of the proposed regression control chart, which was compared with the other procedures consulted. The main contributions of this work may be pointed: (i) the proposal of a method to guide the application of regression control chart; (ii) the adaptation of the multiple regression control chart, allowing the direct monitoring of the quality characteristic; (iii) the proposal of a control chart to monitor the extrapolation of the process control variable and (iv) the obtaining of the ARL of the proposed regression control chart and other similar procedures. The proposed method was applied in a process of a rubber manufactory.