Multiple Hashing Integration for Real-Time Large Scale Part-to-Part Video Matching

A real-time large scale part-to-part video matching algorithm, based on the cross correlation of the intensity of motion curves, is proposed with a view to originality recognition, video database cleansing, copyright enforcement, video tagging or video result re-ranking. Moreover, it is suggested how the most representative hashes and distance functions - strada, discrete cosine transformation, Marr-Hildreth and radial - should be integrated in order for the matching algorithm to be invariant against blur, compression and rotation distortions: (R; _) 2 [1; 20]_[1; 8], from 512_512 to 32_32pixels2 and from 10 to 180_. The DCT hash is invariant against blur and compression up to 64x64 pixels2. Nevertheless, although its performance against rotation is the best, with a success up to 70%, it should be combined with the Marr-Hildreth distance function. With the latter, the image selected by the DCT hash should be at a distance lower than 1.15 times the Marr-Hildreth minimum distance.

3D protein structure matching by patch signatures

For determining functionality dependencies between two proteins, both represented as 3D structures, it is an essential condition that they have one or more matching structural regions called patches. As 3D structures for proteins are large, complex and constantly evolving, it is computationally expensive and very time-consuming to identify possible locations and sizes of patches for a given protein against a large protein database. In this paper, we address a vector space based representation for protein structures, where a patch is formed by the vectors within the region. Based on our previews work, a compact representation of the patch named patch signature is applied here. A similarity measure of two patches is then derived based on their signatures. To achieve fast patch matching in large protein databases, a match-and-expand strategy is proposed. Given a query patch, a set of small k-sized matching patches, called candidate patches, is generated in match stage. The candidate patches are further filtered by enlarging k in expand stage. Our extensive experimental results demonstrate encouraging performances with respect to this biologically critical but previously computationally prohibitive problem.

Bit-index sort: A fast non-comparison integer sorting algorithm for permutations

This paper describes a fast integer sorting algorithm, herein referred to as Bit-index sort, which does not use comparisons and is intended to sort partial permutations. Experimental results exhibit linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers, supported by machine hardware, to retrieve the ordered output sequence. Results show that Bit-index sort outperforms quicksort and counting sort algorithms when compared in their execution time. A parallel approach for Bit-index sort using two simultaneous threads is also included, which obtains further speedups of up to 1.6 compared to its sequential case.

Ciratefi: An RST-invariant template matching with extension to color images

Template matching is a technique widely used for finding patterns in digital images. A good template matching should be able to detect template instances that have undergone geometric transformations. In this paper, we proposed a grayscale template matching algorithm named Ciratefi, invariant to rotation, scale, translation, brightness and contrast and its extension to color images. We introduce CSSIM (color structural similarity) for comparing the similarity of two color image patches and use it in our algorithm. We also describe a scheme to determine automatically the appropriate parameters of our algorithm and use pyramidal structure to improve the scale invariance. We conducted several experiments to compare grayscale and color Ciratefis with SIFT, C-color-SIFT and EasyMatch algorithms in many different situations. The results attest that grayscale and color Ciratefis are more accurate than the compared algorithms and that color-Ciratefi outperforms grayscale Ciratefi most of the time. However, Ciratefi is slower than the other algorithms.

Probabilistic sonar scan matching for an AUV

This paper proposes MSISpIC, a probabilistic sonar scan matching algorithm for the localization of an autonomous underwater vehicle (AUV). The technique uses range scans gathered with a Mechanical Scanning Imaging Sonar (MSIS), the robot displacement estimated through dead-reckoning using a Doppler velocity log (DVL) and a motion reference unit (MRU). The proposed method is an extension of the pIC algorithm. An extended Kalman filter (EKF) is used to estimate the robot-path during the scan in order to reference all the range and bearing measurements as well as their uncertainty to a scan fixed frame before registering. The major contribution consists of experimentally proving that probabilistic sonar scan matching techniques have the potential to improve the DVL-based navigation. The algorithm has been tested on an AUV guided along a 600 m path within an abandoned marina underwater environment with satisfactory results

Model-Based Matching by Linear Combinations of Prototypes

We describe a method for modeling object classes (such as faces) using 2D example images and an algorithm for matching a model to a novel image. The object class models are "learned'' from example images that we call prototypes. In addition to the images, the pixelwise correspondences between a reference prototype and each of the other prototypes must also be provided. Thus a model consists of a linear combination of prototypical shapes and textures. A stochastic gradient descent algorithm is used to match a model to a novel image by minimizing the error between the model and the novel image. Example models are shown as well as example matches to novel images. The robustness of the matching algorithm is also evaluated. The technique can be used for a number of applications including the computation of correspondence between novel images of a certain known class, object recognition, image synthesis and image compression.

Probabilistic sonar scan matching for an AUV

This paper proposes MSISpIC, a probabilistic sonar scan matching algorithm for the localization of an autonomous underwater vehicle (AUV). The technique uses range scans gathered with a Mechanical Scanning Imaging Sonar (MSIS), the robot displacement estimated through dead-reckoning using a Doppler velocity log (DVL) and a motion reference unit (MRU). The proposed method is an extension of the pIC algorithm. An extended Kalman filter (EKF) is used to estimate the robot-path during the scan in order to reference all the range and bearing measurements as well as their uncertainty to a scan fixed frame before registering. The major contribution consists of experimentally proving that probabilistic sonar scan matching techniques have the potential to improve the DVL-based navigation. The algorithm has been tested on an AUV guided along a 600 m path within an abandoned marina underwater environment with satisfactory results

Estimation of Gaussian process regression model using probability distance measures

A new class of parameter estimation algorithms is introduced for Gaussian process regression (GPR) models. It is shown that the integration of the GPR model with probability distance measures of (i) the integrated square error and (ii) Kullback–Leibler (K–L) divergence are analytically tractable. An efficient coordinate descent algorithm is proposed to iteratively estimate the kernel width using golden section search which includes a fast gradient descent algorithm as an inner loop to estimate the noise variance. Numerical examples are included to demonstrate the effectiveness of the new identification approaches.

Three-dimensional reconstruction of fracture surfaces: Area matching algorithms for automatic parallax measurements

This paper describes two solutions for systematic measurement of surface elevation that can be used for both profile and surface reconstructions for quantitative fractography case studies. The first one is developed under Khoros graphical interface environment. It consists of an adaption of the almost classical area matching algorithm, that is based on cross-correlation operations, to the well-known method of parallax measurements from stereo pairs. A normalization function was created to avoid false cross-correlation peaks, driving to the true window best matching solution at each region analyzed on both stereo projections. Some limitations to the use of scanning electron microscopy and the types of surface patterns are also discussed. The second algorithm is based on a spatial correlation function. This solution is implemented under the NIH Image macro programming, combining a good representation for low contrast regions and many improvements on overall user interface and performance. Its advantages and limitations are also presented.

Concept of Matching Parallelepiped and its use in the correspondence problem

In this paper, the concept of Matching Parallelepiped (MP) is presented. It is shown that the volume of the MP can be used as an additional measure of `distance' between a pair of candidate points in a matching algorithm by Relaxation Labeling (RL). The volume of the MP is related with the Epipolar Geometry and the use of this measure works as an epipolar constraint in a RL process, decreasing the efforts in the matching algorithm since it is not necessary to explicitly determine the equations of the epipolar lines and to compute the distance of a candidate point to each epipolar line. As at the beginning of the process the Relative Orientation (RO) parameters are unknown, a initial matching based on gradient, intensities and correlation is obtained. Based on this set of labeled points the RO is determined and the epipolar constraint included in the algorithm. The obtained results shown that the proposed approach is suitable to determine feature-point matching with simultaneous estimation of camera orientation parameters even for the cases where the pair of optical axes are not parallel.

Um estudo sobre o osu do modelo de cor RGB no proceso de correspondência por correlação

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Methodologies for visual correspondence

Visual correspondence is a key computer vision task that aims at identifying projections of the same 3D point into images taken either from different viewpoints or at different time instances. This task has been the subject of intense research activities in the last years in scenarios such as object recognition, motion detection, stereo vision, pattern matching, image registration. The approaches proposed in literature typically aim at improving the state of the art by increasing the reliability, the accuracy or the computational efficiency of visual correspondence algorithms. The research work carried out during the Ph.D. course and presented in this dissertation deals with three specific visual correspondence problems: fast pattern matching, stereo correspondence and robust image matching. The dissertation presents original contributions to the theory of visual correspondence, as well as applications dealing with 3D reconstruction and multi-view video surveillance.

Nonlinear / electromagnetic co-simulation and co-design of microwave links in highly polluted and / or strongly inhomogeneous environments

The objective of the Ph.D. thesis is to put the basis of an all-embracing link analysis procedure that may form a general reference scheme for the future state-of-the-art of RF/microwave link design: it is basically meant as a circuit-level simulation of an entire radio link, with – generally multiple – transmitting and receiving antennas examined by EM analysis. In this way the influence of mutual couplings on the frequency-dependent near-field and far-field performance of each element is fully accounted for. The set of transmitters is treated as a unique nonlinear system loaded by the multiport antenna, and is analyzed by nonlinear circuit techniques. In order to establish the connection between transmitters and receivers, the far-fields incident onto the receivers are evaluated by EM analysis and are combined by extending an available Ray Tracing technique to the link study. EM theory is used to describe the receiving array as a linear active multiport network. Link performances in terms of bit error rate (BER) are eventually verified a posteriori by a fast system-level algorithm. In order to validate the proposed approach, four heterogeneous application contexts are provided. A complete MIMO link design in a realistic propagation scenario is meant to constitute the reference case study. The second one regards the design, optimization and testing of various typologies of rectennas for power generation by common RF sources. Finally, the project and implementation of two typologies of radio identification tags, at X-band and V-band respectively. In all the cases the importance of an exhaustive nonlinear/electromagnetic co-simulation and co-design is demonstrated to be essential for any accurate system performance prediction.

Modelización de reacciones químicas en presencia de un campo electromagnético variable

En esta tesis se aborda el estudio del proceso de isomerización del sistema molecular LiNC/LiCN tanto aislado como en presencia de un pulso láser aplicando la teoría del estado de transición (TST). Esta teoría tiene como pilar fundamental el hecho de que el conocimiento de la dinámica en las proximidades de un punto de silla de la superficie de energía potencial permite determinar los parámetros cinéticos de la reacción objeto de estudio. Históricamente, existen dos formulaciones de la teoría del estado de transición, la versión termodinámica de Eyring (Eyr38) y la visión dinámica de Wigner (Wig38). Ésta última ha sufrido recientemente un amplio desarrollo, paralelo a los avances en sistemas dinámicos que ha dado lugar a una formulación geométrica en el espacio de fases que sirve como base al trabajo desarrollado en esta tesis. Nos hemos centrado en abordar el problema desde una visión fundamentalmente práctica, ya que la teoría del estado de transición presenta una desventaja: su elevado coste computacional y de tiempo de cálculo. Dos han sido los principales objetivos de este trabajo. El primero de ellos ha sido sentar las bases teóricas y computacionales de un algoritmo eficiente que permita obtener las magnitudes fundamentales de la TST. Así, hemos adaptado con éxito un algoritmo computacional desarrollado en el ámbito de la mecánica celeste (Jor99), obteniendo un método rápido y eficiente para la obtención de los objetos geométricos que rigen la dinámica en el espacio de fases y que ha permitido calcular magnitudes cinéticas tales como el flujo reactivo, la densidad de estados de reactivos y productos y en última instancia la constante de velocidad. Dichos cálculos han sido comparados con resultados estadísticos (presentados en (Mül07)) lo cual nos ha permitido demostrar la eficacia del método empleado. El segundo objetivo de esta tesis, ha sido la evaluación de la influencia de los parámetros de un pulso electromagnético sobre la dinámica de reacción. Para ello se ha generalizado la metodología de obtención de la forma normal del hamiltoniano cuando el sistema químico es alterado mediante una perturbación temporal periódica. En este caso el punto fijo inestable en cuya vecindad se calculan los objetos geométricos de interés para la aplicación de la TST, se transforma en una órbita periódica del mismo periodo que la perturbación. Esto ha permitido la simulación de la reactividad en presencia de un pulso láser. Conocer el efecto de esta perturbación posibilita el control de la reactividad química. Además de obtener los objetos geométricos que rigen la dinámica en una cierta vecindad de la órbita periódica y que son la clave de la TST, se ha estudiado el efecto de los parámetros del pulso sobre la reactividad en el espacio de fases global así como sobre el flujo reactivo que atraviesa la superficie divisoria que separa reactivos de productos. Así, se ha puesto de manifiesto, que la amplitud del pulso es el parámetro más influyente sobre la reactividad química, pudiendo producir la aparición de flujos reactivos a energías inferiores a las de aparición del sistema aislado y el aumento del flujo reactivo a valores constantes de energía inicial. ABSTRACT We have studied the isomerization reaction LiNC/LiCN isolated and perturbed by a laser pulse. Transition State theory (TST) is the main tool we have used. The basis of this theory is knowing the dynamics close to a fixed point of the potential energy surface. It is possible to calculate kinetic magnitudes by knowing the dynamics in a neighbourhood of the fixed point. TST was first formulated in the 30's and there were 2 points of view, one thermodynamical by Eyring (Eyr38) and another dynamical one by Wigner (Wig38). The latter one has grown lately due to the growth of the dynamical systems leading to a geometrical view of the TST. This is the basis of the work shown in this thesis. As the TST has one main handicap: the high computational cost, one of the main goals of this work is to find an efficient method. We have adapted a methodology developed in the field of celestial mechanics (Jor99). The result: an efficient, fast and accurate algorithm that allows us to obtain the geometric objects that lead the dynamics close to the fixed point. Flux across the dividing surface, density of states and reaction rate coefficient have been calculated and compared with previous statistical results, (Mül07), leading to the conclusion that the method is accurate and good enough. We have widen the methodology to include a time dependent perturbation. If the perturbation is periodic in time, the fixed point becomes a periodic orbit whose period is the same as the period of the perturbation. This way we have been able to simulate the isomerization reaction when the system has been perturbed by a laser pulse. By knowing the effect of that perturbation we will be able to control the chemical reactivity. We have also studied the effect of the parameters on the global phase space dynamics and on the flux across the dividing surface. It has been prove that amplitude is the most influent parameter on the reaction dynamics. Increasing amplitude leads to greater fluxes and to some flux at energies it would not if the systems would not have been perturbed.

Shift, scaling and derivative properties for the discrete cosine transform

A set of DCT domain properties for shifting and scaling by real amounts, and taking linear operations such as differentiation is described. The DCT coefficients of a sampled signal are subjected to a linear transform, which returns the DCT coefficients of the shifted, scaled and/or differentiated signal. The properties are derived by considering the inverse discrete transform as a cosine series expansion of the original continuous signal, assuming sampling in accordance with the Nyquist criterion. This approach can be applied in the signal domain, to give, for example, DCT based interpolation or derivatives. The same approach can be taken in decoding from the DCT to give, for example, derivatives in the signal domain. The techniques may prove useful in compressed domain processing applications, and are interesting because they allow operations from the continuous domain such as differentiation to be implemented in the discrete domain. An image matching algorithm illustrates the use of the properties, with improvements in computation time and matching quality.