A video sequence consists of a series of frames. In order to compress the video for efficient storage and transmission, the temporal redundancy among adjacent frames must be exploited. A frame is selected as reference frame and subsequent frames are predicted from the reference frame using a technique known as motion estimation. Real videos contain a mixture of motions with slow and fast contents. Among block matching motion estimation algorithms, the full search algorithm is known for its superiority in the performance over other matching techniques. However, this method is computationally very extensive. Several fast block matching algorithms (FBMAs) have been proposed in the literature with the aim to reduce computational costs while maintaining desired quality performance, but all these methods are considered to be sub-optimal. No fixed fast block matching algorithm can effi- ciently remove temporal redundancy of video sequences with wide motion contents. Adaptive fast block matching algorithm, called classification based adaptive search (CBAS) has been proposed. A Bayes classifier is applied to classify the motions into slow and fast categories. Accordingly, appropriate search strategy is applied for each class. The algorithm switches between different search patterns according to the content of motions within video frames. The proposed technique outperforms conventional stand-alone fast block matching methods in terms of both peak signal to noise ratio (PSNR) and computational complexity. In addition, a new hierarchical method for detecting and classifying shot boundaries in video sequences is proposed which is based on information theoretic classification (ITC). ITC relies on likelihood of class label transmission of a data point to the data points in its vicinity. ITC focuses on maximizing the global transmission of true class labels and classify the frames into classes of cuts and non-cuts. Applying the same rule, the non-cut frames are also classified into two categories of arbitrary shot frames and gradual transition frames. CBAS is applied on the proposed shot detection method to handle camera or object motions. Experimental evidence demonstrates that our method can detect shot breaks with high accuracy.

A video sequence consists of a series of frames. In order to compress the video for efficient storage and transmission, the temporal redundancy among adjacent frames must be exploited. A frame is selected as reference frame and subsequent frames are predicted from the reference frame using a technique known as motion estimation. Real videos contain a mixture of motions with slow and fast contents. Among block matching motion estimation algorithms, the full search algorithm is known for its superiority in the performance over other matching techniques. However, this method is computationally very extensive. Several fast block matching algorithms (FBMAs) have been proposed in the literature with the aim to reduce computational costs while maintaining desired quality performance, but all these methods are considered to be sub-optimal. No fixed fast block matching algorithm can effi- ciently remove temporal redundancy of video sequences with wide motion contents. Adaptive fast block matching algorithm, called classification based adaptive search (CBAS) has been proposed. A Bayes classifier is applied to classify the motions into slow and fast categories. Accordingly, appropriate search strategy is applied for each class. The algorithm switches between different search patterns according to the content of motions within video frames. The proposed technique outperforms conventional stand-alone fast block matching methods in terms of both peak signal to noise ratio (PSNR) and computational complexity. In addition, a new hierarchical method for detecting and classifying shot boundaries in video sequences is proposed which is based on information theoretic classification (ITC). ITC relies on likelihood of class label transmission of a data point to the data points in its vicinity. ITC focuses on maximizing the global transmission of true class labels and classify the frames into classes of cuts and non-cuts. Applying the same rule, the non-cut frames are also classified into two categories of arbitrary shot frames and gradual transition frames. CBAS is applied on the proposed shot detection method to handle camera or object motions. Experimental evidence demonstrates that our method can detect shot breaks with high accuracy.

Due to the progress of Internet technology and technical improvement, the growths of multimedia products and services ,such as Multimedia Message Service¡]MMS¡^, Multimedia on Demand¡]MoD¡^, Video Conferencing, and Digital TV, are very fast. All of these services need good video compression and audio compression standards to support. It is impossible to transmit source data of multimedia on networks. Motion Estimation needs the most computing complexity in the video compression. In our research, we focus on how to reduce candidate blocks and keep video quality. We study some fast motion estimation algorithms and architectures, and design a fast motion estimation architecture which supports resolution of 1280x720 at 30fps frame rate in HDTV specification based on hierarchical motion estimation algorithm. In the limit of hardware resources and the compressed video quality, the architecture can improve inter-coding performance. Two adjacent MacroBlocks have similar Motion Vector in our observation. We arrange a 16x8 processing element array to deal with two adjacent MacroBlocks together. The design can reduce a lot of clock cycles in the hierarchical motion estimation architecture, and keep high video quality. Furthermore, we propose a search range prediction method¡]called ASR¡^which reflect the motion behavior of video sequences into search range on MB-By-MB Basis. ASR can reduce the unnecessary operation of candidate blocks and keep very high video quality compared with Full Search Block Matching algorithm by the implementation in official software of the new video compression standard, Joint Model of H.264/AVC.

In this thesis we use greedy randomize adaptive search procedure (GRASP) to solve the traveling salesman problem (TSP). Starting with nearest neighbor method to construct the initial TSP tour, we apply the 2-opt and the path-relinking method for the initial tour improvement. To increase 2-opt search speed, fixed-radius near neighbor search and don0t − look bit techniques are introduced. For the same reason a new efficient data structure, the reverse array, is proposed to represent the TSP tour. Computational results show that GRASP gives fairly good solutions in a short time.

Made available in DSpace on 2015-05-14T12:36:40Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2336902 bytes, checksum: 41580878008a0f84da693637a48ceb33 (MD5) Previous issue date: 2013-08-08 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The present work deals with the Continuous Global Optimization Problem, in its minimization form, by testing two approaches for the Continuous Greedy Randomized Adaptive Search Procedure (C-GRASP). The development of the first method - sequential and hybrid - comes from the deficiency of current approaches to provide a good neighborhood space exploration. Being constructed from the combination of two meta-heuristics, standard C-GRASP and Continuous General Variable Neighborhood Search (C-GVNS), as a strategy to achieving symmetric trades of neighborhood structures, it performed efficiently in the computational tests that were taken. The second procedure arises from the large consume of time when using high dimension functions with the standard C-GRASP construction procedure. As the optimization problems have a high dimensionality increase, it s preferable to have two parallel versions of the optimization method in order to handle bigger problems. Thus, for this new procedure developed, it was used the Compute Unified Device Architecture (CUDA), which provided promising acceleration regarding the processing time, based on the experiments performed. / O presente trabalho aborda o Problema de Otimização Global Contínua, em sua forma de minimização, através de duas abordagens para o procedimento Continuous Greedy Randomized Adaptive Search Procedure (C-GRASP). A elaboração do primeiro método, sequencial e híbrido, parte da deficiência presente nas abordagens atuais, em promover boa exploração no espaço de vizinhança. Sendo constituída da combinação de duas meta-heurísticas, C-GRASP padrão e Continuous General Variable Neighborhood Search (C-GVNS). Como estratégia para a realização de trocas sistemática de estruturas de vizinhanças, mostrou-se eficiente aos testes computacionais realizados. O segundo procedimento elaborado parte do grande consumo de tempo ao utilizar funções com alta dimensão, pelo procedimento de construção do método C-GRASP padrão. Como os problemas de otimização possuem crescimento elevado de dimensionalidade, é desejável ter versões paralelas do método de otimização para lidar com os problemas maiores. Desta forma, para o novo procedimento elaborado foi empregado a plataforma de computação paralela Compute Unified Device Architecture (CUDA), que, conforme verificado nos experimentos realizados, promoveu promissora aceleração quanto ao tempo de processamento.

Planning and scheduling in semiconductor manufacturing is a difficult problem due to long cycle times, a large number of operational steps, diversified product types, and low-volume high-mix customer demand. This research addresses several problems that arise in the semiconductor industry related to front-end wafer fabrication operations and back-end assembly and test operations. The mathematical models built for these problems turn out to be large-scale mixed integer programs and hard to solve with exact methods. The major contribution of this research is to combine mathematical programming with metaheuristics to find high quality solutions within the time limits imposed by the industrial engineers who oversee the fabrication and test facilities. In order to reduce the size of problems that arise in practice, it is common to cluster similar product types into groups that reflect their underlying technology. The first part of the research is aimed at developing a greedy randomized adaptive search procedure (GRASP) coupled with path relinking (PR) to solve the capacitated clustering problem. The model is generic and can be applied in many different situations. The objective is to maximize a similarity measure within each cluster such that the sum of the weights associated with the product types does not exceed the cluster capacity in each case. In phase I, both a heaviest weight edge (HWE) algorithm and a constrained minimum cut (CMC) algorithm are used to select seeds for initializing the clusters. Feasible solutions are obtained with the help of a self-adjusting restricted candidate list. In phase II, three neighborhoods are defined and explored using the following strategies: cyclic neighborhood search, variable neighborhood descent, and randomized variable neighborhood descent (RVND). The best solutions found are stored in an elite pool. In a post-processing step, PR coupled with local search is applied to the pool members to cyclically generate paths between each pair. The elite pool is updated after each iteration and the procedure ends when no further improvement is possible. After grouping the product types into technologies, a new model is presented for production planning in a high volume fab that uses quarterly commitments to define daily target outputs. Rather than relying on due dates and priority rules to schedule lot starts and move work in process through the shop, the objective is to minimize the sum of the deviations between the target outputs and finished goods inventory. The model takes the form of a large-scale linear program that is intractable for planning horizons beyond a few days. Both Lagrangian relaxation and Benders decomposition were investigated but each proved ineffective. As a consequence, a methodology was developed which was more tailored to the problem’s structure. This involved creating weekly subproblems that were myopic but could be solved to optimality within a few minutes, and then postprocessing the results with a decomposition algorithm to fully utilize the excessive machine time. The heart of the post-processor consists of a rescheduling algorithm and a dispatching heuristic. The third part of the research focuses on the combinatorial problem of machinetooling setup and lot assignments for performing back-end operations. A new model and solution methodology are presented aimed at maximizing the weighted throughput of lots undergoing assembly and test, while ensuring that critical lots are given priority. The problem is formulated as a mixed-integer program and solved again with a GRASP that makes use of linear programming. In phase I of the GRASP, machine-tooling combinations are tentatively fixed and lot assignments are made iteratively to arrive at a feasible solution. This process is repeated many times. In phase II, a novel neighborhood search is performed on a subset of good solutions found in phase I. Using a linear programming-Monte Carlo simulation-based algorithm, new machine-tooling combinations are identified within the neighborhood of the solutions carried over, and improvements are sought by optimizing the corresponding lot assignments. / text

Made available in DSpace on 2015-05-14T12:36:51Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1355559 bytes, checksum: fe1c88470e43ce75f706ec9d15cc7bb1 (MD5) Previous issue date: 2014-07-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / With the advent of technological advances, increasingly demand solutions that use fewer resources, are faster and low cost. As a result, this paper proposed a hybrid approach using metaheuristics Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Local Search (ILS) applied to the Response Time Variability Problem (RTVP). Since this problem may involve allocation of scarce resources, such as industrial machinery or meeting rooms, going for scheduling of banking customers that require certain conditions, planning of TV ads or route taken by vehicles of logistic companies, etc. For application of the procedure, the movements of shifting symbols, swapping positions between symbols and one called double bridge, which is a mix of movements of shifting and swapping involving opposite symbols were used. The neighborhood structures were based on the movements described above, varying the number of symbols involved. Thus, the results obtained demonstrate that such procedures satisfied the problem and brought consistent results when compared with the literature. / Com o advento dos avanços tecnológicos, cada vez mais se procura soluções que utilizem menos recursos, sejam mais rápidos e de baixo custo. Em virtude disso, este trabalho propôs uma abordagem meta-heurística híbrida utilizando Greedy Randomized Adaptive Search Procedure (GRASP) e Iterated Local Search (ILS) aplicados ao Problema da Variabilidade do Tempo de Resposta. Este problema pode envolver desde alocação de recursos escassos, como por exemplo, máquinas industriais ou salas de reunião, passando pelo agendamento de clientes de um banco que requerem certas condições, o planejamento das propagandas de TV ou o percurso feito por caminhões de empresas transportadoras, dentre outros. Para a aplicação do procedimento, foram utilizados os movimentos de deslocamento do mesmo, permuta de posição entre símbolos e de um movimento chamado double brigde, que é uma mistura dos movimentos de deslocamento e permutação envolvendo símbolos opostos. As estruturas de vizinhança compostas basearam-se nos movimentos descritos anteriormente, variando a quantidade de símbolos envolvidos. Desta forma, os resultados obtidos demonstram que tais procedimentos trouxeram resultados satisfatórios ao problema e condizentes quando comparados com a literatura.

The continuous growth of traffic demand driven by the brisk increase in number of Internet users and emerging online services creates new challenges for communication networks. The latest advances in Wavelength Division Multiplexing (WDM) technology make it possible to build Transparent Optical Networks (TONs) which are expected to be able to satisfy this rapidly growing capacity demand. Moreover, with the ability of TONs to transparently carry the optical signal from source to destination, electronic processing of the tremendous amount of data can be avoided and optical-to-electrical-to-optical (O/E/O) conversion at intermediate nodes can be eliminated. Consequently, transparent WDM networks consume relatively low power, compared to their electronic-based IP network counterpart. Furthermore, TONs bring also additional benefits in terms of bit rate, signal format, and protocol transparency. However, the absence of O/E/O processing at intermediate nodes in TONs has also some drawbacks. Without regeneration, the quality of the optical signal transmitted from a source to a destination might be degraded due to the effect of physical-layer impairments induced by the transmission through optical fibers and network components. For this reason, routing approaches specifically tailored to account for the effect of physical-layer impairments are needed to avoid setting up connections that don’t satisfy required signal quality at the receiver. Transparency also makes TONs highly vulnerable to deliberate physical-layer attacks. Malicious attacking signals can cause a severe impact on the traffic and for this reason proactive mechanisms, e.g., network design strategies, able to limit their effect are required. Finally, even though energy consumption of transparent WDM networks is lower than in the case of networks processing the traffic at the nodes in the electronic domain, they have the potential to consume even less power. This can be accomplished by targeting the inefficiencies of the current provisioning strategies applied in WDM networks. The work in this thesis addresses the three important aspects mentioned above. In particular, this thesis focuses on routing and wavelength assignment (RWA) strategies specifically devised to target: (i) the lightpath transmission quality, (ii) the network security (i.e., in terms of vulnerability to physical-layer attacks), and (iii) the reduction of the network energy consumption. Our contributions are summarized below. A number of Impairment Constraint Based Routing (ICBR) algorithms have been proposed in the literature to consider physical-layer impairments during the connection provisioning phase. Their objective is to prevent the selection of optical connections (referred to as lightpaths) with poor signal quality. These ICBR approaches always assign each connection request the least impaired lightpath and support only a single threshold of transmission quality, used for all connection requests. However, next generation networks are expected to support a variety of services with disparate requirements for transmission quality. To address this issue, in this thesis we propose an ICBR algorithm supporting differentiation of services at the Bit Error Rate (BER) level, referred to as ICBR-Diff. Our approach takes into account the effect of physical-layer impairments during the connection provisioning phase where various BER thresholds are considered for accepting/blocking connection requests, depending on the signal quality requirements of the connection requests. We tested the proposed ICBR-Diff approach in different network scenarios, including also a fiber heterogeneity. It is shown that it can achieve a significant improvement of network performance in terms of connection blocking, compared to previously published non-differentiated RWA and ICBR algorithms.  Another important challenge to be considered in TONs is their vulnerability to physical-layer attacks. Deliberate attacking signals, e.g., high-power jamming, can cause severe service disruption or even service denial, due to their ability to propagate in the network. Detecting and locating the source of such attacks is difficult, since monitoring must be done in the optical domain, and it is also very expensive. Several attack-aware RWA algorithms have been proposed in the literature to proactively reduce the disruption caused by high-power jamming attacks. However, even with attack-aware network planning mechanisms, the uncontrollable propagation of the attack still remains an issue. To address this problem, we propose the use of power equalizers inside the network nodes in order to limit the propagation of high-power jamming attacks. Because of the high cost of such equipment, we develop a series of heuristics (incl. Greedy Randomized Adaptive Search Procedure (GRASP)) aiming at minimizing the number of power equalizers needed to reduce the network attack vulnerability to a desired level by optimizing the location of the equalizers. Our simulation results show that the equalizer placement obtained by the proposed GRASP approach allows for 50% reduction of the sites with the power equalizers while offering the same level of attack propagation limitation as it is possible to achieve with all nodes having this additional equipment installed. In turn, this potentially yields a significant cost saving.    Energy consumption in TONs has been the target of several studies focusing on the energy-aware and survivable network design problem for both dedicated and shared path protection. However, survivability and energy efficiency in a dynamic provisioning scenario has not been addressed. To fill this gap, in this thesis we focus on the power consumption of survivable WDM network with dynamically provisioned 1:1 dedicated path protected connections. We first investigate the potential energy savings that are achievable by setting all unused protection resources into a lower-power, stand-by state (or sleep mode) during normal network operations. It is shown that in this way the network power consumption can be significantly reduced. Thus, to optimize the energy savings, we propose and evaluate a series of energy-efficient strategies, specifically tailored around the sleep mode functionality. The performance evaluation results reveal the existence of a trade-off between energy saving and connection blocking. Nonetheless, they also show that with the right provisioning strategy it is possible to save a considerable amount of energy with a negligible impact on the connection blocking probability. In order to evaluate the performance of our proposed ICBR-Diff and energy-aware RWA algorithms, we develop two custom-made discrete-event simulators. In addition, the Matlab program of GRASP approach for power equalization placement problem is implemented. / <p>QC 20120508</p>