This thesis presents the rate distortion analysis of conditional motion estimation, a process in which motion computation is restricted to only active pixels in the video. We model active pixels as independent and identically distributed Gaussian process and inactive pixels as Gaussian-Markov process and derive the rate distortion function based on conditional motion estimation. Rate-Distortion curves for the conditional motion estimation scheme are also presented. In addition this thesis also presents the hardware implementation of a block based motion estimation algorithm. Block matching algorithms are difficult to implement on FPGA chip due to its complexity. We implement 2D-Logarithmic search algorithm to estimate the motion vectors for the image. The matching criterion used in the algorithm is Sum of Absolute Differences (SAD). VHDL code for the motion estimation algorithm is verified using ISim and is implemented using Xilinx ISE Design tool. Synthesis results for the algorithm are also presented.

Design optimization of structures has become an important method to study and develop these days. Due to the fact that the world's population is increasing, and the worlds' resources are decreasing. An optimum design algorithm is a useful tool that can help to minimize the weight of a structure. Over the last four decades, several number of algorithms have been developed to solve engineering optimization problems, for example, metaheuristic algorithms. An example of metaheuristic algorithms is the Harmony Search algorithm (HS). HS algorithms make use of the analogy between the performance process of natural music and searching for solutions to optimization problems. In this research, the HS was applied on the College of Engineering Building at Temple University Main Campus in Philadelphia, PA. The HS algorithm searches for minimum cross-sectional areas that leads to find optimal steel sizes considering design constrains such as: stress, deflection, and lateral displacement limitations. The HS algorithm obtained lighter weight of steel frames by selecting a suitable steel section from the American Institute of Steel Construction (AISC) and by following the specification of Allowable Stress Design method (ASD). The results show that HS yielded lighter steel moment frames with approximately 20% weight reduction. Keywords: Harmony Search Algorithm, Steel Moment Frame, Optimization. / Civil Engineering

O propósito deste trabalho foi o de elaborar uma metodologia de projeto de embarcações pesqueiras como alternativa ao processo clássico baseado na seqüência da \"Espiral de Projetos\". A metodologia proposta faz uso de um algoritmo de otimização que tem como finalidade automatizar cada uma das etapas e aperfeiçoar o resultado final mediante a busca, dentro do espaço de soluções viáveis (chamadas de soluções satisfatórias), da solução \"ótima\", ou seja, a melhor solução para uma determinada condição. Devido ao fato de cada zona de pesca ter suas características particulares no que diz respeito a condições ambientais (altura das ondas e força do vento), arte de pesca desenvolvida na região e normas impostas pela Autoridade Marítima, foi feita, em particular, uma aplicação ao caso da pesca no litoral peruano, pois foram consideradas no desenvolvimento do trabalho peculiaridades e dados que estão presentes nesta região. Neste sentido, desenvolveu-se um programa automatizado e otimizado baseado em uma seqüência de cálculos que permite projetar, a partir dos requisitos do armador, as características de uma embarcação pesqueira que cumpre um conjunto de restrições impostas e que atende ao objetivo desejado, ou seja, a embarcação que represente, através dessas características, a melhor solução possível para uma função de mérito ou função objetivo imposta. Desta forma, utilizando a técnica da parametrização de embarcações semelhantes, assim como métodos conhecidos para cálculo de características e atributos associados a navios pesqueiros, e também um algoritmo matemático de busca, demonstrou-se que é possível projetar uma embarcação pesqueira, do tipo de cerco, a partir dos requisitos do armador, com bons resultados, em períodos curtos de tempo e dentro das margens esperadas em etapas preliminares de projeto. / The purpose of this work was to develop a methodology for a fishing vessel design as alternative to the classic process based on the sequence of the \"Design Spiral.\" The proposed methodology use an optimization algorithm that aims to automate each one of the stages of the design and to improve the final result by the search, among the space of viable solutions (calls of satisfactory solutions), of the optimal solution, in other words, to find the best solution for a determined condition. Due to different characteristics of each fishing area such as: environmental conditions (height of the waves and wind intensity), the fishing gear used in the region and the rules established by the local Maritime Authority, this tool contemplates specific applications to fishing in the Peruvian coasts. Therefore, the development of this tool considered the corresponding data available for the region and the particularities unique to this fishing ground. In this context, an automated and optimized program was created based on a sequence of calculations, allowing to project, under the owner\'s requirements, fitting the characteristics of a fishing vessel that contemplates the imposed restrictions while achieving the overall objective. In other words, the resulting vessel will achieve, through these characteristics, the best possible solution in terms of functionality and desired requirements. Therefore, using the parametric technique of similar vessels, as well as known methods for the calculation of characteristics and associated attributes for fishing vessels and the use of a search mathematical algorithm, it was demonstrated that it is possible to design a fishing vessel of the seiner type, from the requirements of the owner, with good results, in few periods of time and within expected rates in preliminary stages of the project.

We consider the lower-bounded facility location (LBFL) problem (, also known as load-balanced facility location), which is a generalization of uncapacitated facility location (UFL) problem where each open facility is required to serve a minimum number of clients. More formally, in the LBFL problem, we are given a set of clients Ɗ , a set of facilities Ƒ, a non-negative facility-opening cost f_i for each i ∈ Ƒ, a lower bound M, and a distance metric c(i,j) on the set Ɗ ∪ Ƒ, where c(i,j) denotes the cost of assigning client j to facility i. A feasible solution S specifies the set of open facilities F_S ⊆ Ƒ and the assignment of each client j to an open facility i(j) such that each open facility serves at least M clients. Our goal is to find feasible solution S that minimizes ∑_{i ∈ F_S} f_i + ∑_j c(i,j). The current best approximation ratio for LBFL is 550. We substantially advance the state-of-the-art for LBFL by devising an approximation algorithm for LBFL that achieves a significantly-improved approximation guarantee of 83.

To determine the maximum rectangular block (MRB) from a rare material as larger as possible indicates to increase of the rate of material usage. The cutting problem has been addressed since 1984. But its applications were strongly restricted due to simple definition of the cutting problem. In order to expand the area of applications, in this dissertation, a general cutting problem will be considered. At first, the rectangular boundary of the original material is replaced by an arbitrary closed region. Due to the general material profile, many other materials can be involved. When the maximum rectangular block has been obtained, the remaining closed space (RCS) of the material can be divided again. A blind search algorithm (BSA), which globally searches the MRB point-by-point from the boundary points of the contour, will be developed. The BSA is able to acquire the MRB from mother material continuously from larger areas to smaller ones until a predefined threshold value is reached. Although the MRB in an arbitrary closed region can be successfully resolved, two problems are still unsolved. The first limitation is that both edges of the MRB must be parallel with image axes. The second limitation is that the mother material needs to be uniform, i.e., no defects inside the material. In order to release these two assumptions, some algorithms will be presented. Applications of those techniques to the leather material will be demonstrated. In spite of resolving the cutting problem by the presented algorithms, a possible improvement is needed for larger MRBs. The challenge about larger MRBs is that how to make the searching process more efficiently. Therefore, two new methods of GA to obtain the MRB are proposed. By comparing the results using the BSA, the GA approaches are verified to be able to reach the near-optimal performance. Even though only leather material is focused in this research, the proposed methods can be easily extended to other industrial materials, especially for those expensive materials.

We consider the lower-bounded facility location (LBFL) problem (, also known as load-balanced facility location), which is a generalization of uncapacitated facility location (UFL) problem where each open facility is required to serve a minimum number of clients. More formally, in the LBFL problem, we are given a set of clients Ɗ , a set of facilities Ƒ, a non-negative facility-opening cost f_i for each i ∈ Ƒ, a lower bound M, and a distance metric c(i,j) on the set Ɗ ∪ Ƒ, where c(i,j) denotes the cost of assigning client j to facility i. A feasible solution S specifies the set of open facilities F_S ⊆ Ƒ and the assignment of each client j to an open facility i(j) such that each open facility serves at least M clients. Our goal is to find feasible solution S that minimizes ∑_{i ∈ F_S} f_i + ∑_j c(i,j). The current best approximation ratio for LBFL is 550. We substantially advance the state-of-the-art for LBFL by devising an approximation algorithm for LBFL that achieves a significantly-improved approximation guarantee of 83.

O propósito deste trabalho foi o de elaborar uma metodologia de projeto de embarcações pesqueiras como alternativa ao processo clássico baseado na seqüência da \"Espiral de Projetos\". A metodologia proposta faz uso de um algoritmo de otimização que tem como finalidade automatizar cada uma das etapas e aperfeiçoar o resultado final mediante a busca, dentro do espaço de soluções viáveis (chamadas de soluções satisfatórias), da solução \"ótima\", ou seja, a melhor solução para uma determinada condição. Devido ao fato de cada zona de pesca ter suas características particulares no que diz respeito a condições ambientais (altura das ondas e força do vento), arte de pesca desenvolvida na região e normas impostas pela Autoridade Marítima, foi feita, em particular, uma aplicação ao caso da pesca no litoral peruano, pois foram consideradas no desenvolvimento do trabalho peculiaridades e dados que estão presentes nesta região. Neste sentido, desenvolveu-se um programa automatizado e otimizado baseado em uma seqüência de cálculos que permite projetar, a partir dos requisitos do armador, as características de uma embarcação pesqueira que cumpre um conjunto de restrições impostas e que atende ao objetivo desejado, ou seja, a embarcação que represente, através dessas características, a melhor solução possível para uma função de mérito ou função objetivo imposta. Desta forma, utilizando a técnica da parametrização de embarcações semelhantes, assim como métodos conhecidos para cálculo de características e atributos associados a navios pesqueiros, e também um algoritmo matemático de busca, demonstrou-se que é possível projetar uma embarcação pesqueira, do tipo de cerco, a partir dos requisitos do armador, com bons resultados, em períodos curtos de tempo e dentro das margens esperadas em etapas preliminares de projeto. / The purpose of this work was to develop a methodology for a fishing vessel design as alternative to the classic process based on the sequence of the \"Design Spiral.\" The proposed methodology use an optimization algorithm that aims to automate each one of the stages of the design and to improve the final result by the search, among the space of viable solutions (calls of satisfactory solutions), of the optimal solution, in other words, to find the best solution for a determined condition. Due to different characteristics of each fishing area such as: environmental conditions (height of the waves and wind intensity), the fishing gear used in the region and the rules established by the local Maritime Authority, this tool contemplates specific applications to fishing in the Peruvian coasts. Therefore, the development of this tool considered the corresponding data available for the region and the particularities unique to this fishing ground. In this context, an automated and optimized program was created based on a sequence of calculations, allowing to project, under the owner\'s requirements, fitting the characteristics of a fishing vessel that contemplates the imposed restrictions while achieving the overall objective. In other words, the resulting vessel will achieve, through these characteristics, the best possible solution in terms of functionality and desired requirements. Therefore, using the parametric technique of similar vessels, as well as known methods for the calculation of characteristics and associated attributes for fishing vessels and the use of a search mathematical algorithm, it was demonstrated that it is possible to design a fishing vessel of the seiner type, from the requirements of the owner, with good results, in few periods of time and within expected rates in preliminary stages of the project.

The study of Stochastic Local Search (SLS) algorithms is becoming more pivotal these days, due to their vast number of applications in decision making. Prior to the implementation of algorithmic knowledge for decision making, many decisions were made based on manual calculation, on the fly, or even based on guts feeling. Nowadays, such an approach is more rarely seen, especially when the decisions that need to be made are high-risk, cost intensive, or time-consuming. The increasingly often used SLS algorithms are one of the options available to assist the decision making process these days.The work discussed in this thesis concerns the study of SLS algorithms for solving the Quadratic Assignment Problem (QAP), a prominent combinatorial optimization problem, which until today is very hard to solve. Our interest is to study the behavior and performance of SLS algorithms for solving QAP instances of different characteristics, such as size, sparsity, and structure. In this study, we have also proposed new variants of SLS algorithms, inspired by existing, well-performing SLS algorithms for solving the QAP. The new variants of SLS algorithms are then further extended for solving the bi-objective QAP (bQAP).One main focus in this study is to see how the performance of algorithms scales with instance size. We have considered instances that are much larger than the ones usually used in the studies of algorithms for solving the QAP. By understanding how the algorithms perform when the instance size changes, we might be able to solve other problems effectively by considering the similarity in their characteristics to the ones of the QAP, or by seeing common trends in the relative performance of the various available SLS methods. For single objective QAP instances we found that the structure and size of instances do have a significant impact on the performance of SLS algorithms. For example, comparisons between Tabu Search (TS) and Simulated Annealing (SA) on instances with randomly generated matrices show that the overall performance of TS is better than SA, irrespective the size of instances considered. The results on a class of structured instances however show that TS performs well on small-sized instances, while on the larger ones, SA shows better results. In another experiment, Hierarchical Iterated Local Search (HILS) has shown very good results compared to several Iterated Local Search (ILS) variants. This experiment was done on a class of structured instances of size from 100 to 500. An extensive experiment on a class of structured instances of size 30 to 300 using tuned parameter settings shows that population based algorithms perform very well on most of the instance classes considered. SA however, shows very good performance especially on large-sized instances with low sparsity level. For the bQAP, the correlation between the flow matrices does have a strong effect that determines the performance of algorithms for solving them. Hybrid Simulated Annealing (HSA) clearly outperforms Hybrid Iterative Improvement (HII). When compared to Multi Objective Ant Colony Optimization (MOACO) and Strength Pareto Evolutionary Algorithm 2 (SPEA2), HSA shows very good performance, where HSA outperforms MOACO and SPEA2, especially on instances of large size, thus, offering a better scaling behavior. Based the results obtained in this study, it is possible to come up with a general idea on the suitability of SLS algorithms for solving instances with a certain characteristic. Given an unknown QAP instance, one can guess the most suitable algorithm for solving it depending on the type, size, and sparsity of the instance, while for a bQAP instance the most suitable algorithm can be guessed based on its size and correlation between the flow matrices. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

No description available.

The diploma thesis deals with creating of electronic schematics in editor using web interface. The editor generates electrical circuit text file according to Spice netlist specification. The program has been created in Java and takes an advantage of object oriented programming language. The editor is a part of a web page and is executable as an applet. The diploma thesis describes a programming language selection, program layout and implementation. Thesis contains programming code examples, window illustration and component drawings. Depth-first search algorithm has been used for nodes number assignment. An OrCAD PSpice reference guide was used for netlist.