Hierarchical indexing structure for efficient similarity search in video retrieval

With the rapid increase in both centralized video archives and distributed WWW video resources, content-based video retrieval is gaining its importance. To support such applications efficiently, content-based video indexing must be addressed. Typically, each video is represented by a sequence of frames. Due to the high dimensionality of frame representation and the large number of frames, video indexing introduces an additional degree of complexity. In this paper, we address the problem of content-based video indexing and propose an efficient solution, called the Ordered VA-File (OVA-File) based on the VA-file. OVA-File is a hierarchical structure and has two novel features: 1) partitioning the whole file into slices such that only a small number of slices are accessed and checked during k Nearest Neighbor (kNN) search and 2) efficient handling of insertions of new vectors into the OVA-File, such that the average distance between the new vectors and those approximations near that position is minimized. To facilitate a search, we present an efficient approximate kNN algorithm named Ordered VA-LOW (OVA-LOW) based on the proposed OVA-File. OVA-LOW first chooses possible OVA-Slices by ranking the distances between their corresponding centers and the query vector, and then visits all approximations in the selected OVA-Slices to work out approximate kNN. The number of possible OVA-Slices is controlled by a user-defined parameter delta. By adjusting delta, OVA-LOW provides a trade-off between the query cost and the result quality. Query by video clip consisting of multiple frames is also discussed. Extensive experimental studies using real video data sets were conducted and the results showed that our methods can yield a significant speed-up over an existing VA-file-based method and iDistance with high query result quality. Furthermore, by incorporating temporal correlation of video content, our methods achieved much more efficient performance.

Excitation spectra of the spin-1/2 triangular-lattice Heisenberg antiferromagnet

We use series expansion methods to calculate the dispersion relation of the one-magnon excitations for the spin-(1)/(2) triangular-lattice nearest-neighbor Heisenberg antiferromagnet above a three-sublattice ordered ground state. Several striking features are observed compared to the classical (large-S) spin-wave spectra. Whereas, at low energies the dispersion is only weakly renormalized by quantum fluctuations, significant anomalies are observed at high energies. In particular, we find rotonlike minima at special wave vectors and strong downward renormalization in large parts of the Brillouin zone, leading to very flat or dispersionless modes. We present detailed comparison of our calculated excitation energies in the Brillouin zone with the spin-wave dispersion to order 1/S calculated recently by Starykh, Chubukov, and Abanov [Phys. Rev. B74, 180403(R) (2006)]. We find many common features but also some quantitative and qualitative differences. We show that at temperatures as low as 0.1J the thermally excited rotons make a significant contribution to the entropy. Consequently, unlike for the square lattice model, a nonlinear sigma model description of the finite-temperature properties is only applicable at temperatures < 0.1J. Finally, we review recent NMR measurements on the organic compound kappa-(BEDT-TTF)(2)Cu-2(CN)(3). We argue that these are inconsistent with long-range order and a description of the low-energy excitations in terms of interacting magnons, and that therefore a Heisenberg model with only nearest-neighbor exchange does not offer an adequate description of this material.

Expansion-based algorithms for finding single pair shortest path on surface

Finding single pair shortest paths on surface is a fundamental problem in various domains, like Geographic Information Systems (GIS) 3D applications, robotic path planning system, and surface nearest neighbor query in spatial database, etc. Currently, to solve the problem, existing algorithms must traverse the entire polyhedral surface. With the rapid advance in areas like Global Positioning System (CPS), Computer Aided Design (CAD) systems and laser range scanner, surface models axe becoming more and more complex. It is not uncommon that a surface model contains millions of polygons. The single pair shortest path problem is getting harder and harder to solve. Based on the observation that the single pair shortest path is in the locality, we propose in this paper efficient methods by excluding part of the surface model without considering them in the search process. Three novel expansion-based algorithms are proposed, namely, Naive algorithm, Rectangle-based Algorithm and Ellipse-based Algorithm. Each algorithm uses a two-step approach to find the shortest path. (1) compute an initial local path. (2) use the value of this initial path to select a search region, in which the global shortest path exists. The search process terminates once the global optimum criteria are satisfied. By reducing the searching region, the performance is improved dramatically in most cases.

Maximum-likelihood noncoherent lattice decoding of QAM

We present a novel, maximum-likelihood (ML), lattice-decoding algorithm for noncoherent block detection of QAM signals. The computational complexity is polynomial in the block length; making it feasible for implementation compared with the exhaustive search ML detector. The algorithm works by enumerating the nearest neighbor regions for a plane defined by the received vector; in a conceptually similar manner to sphere decoding. Simulations show that the new algorithm significantly outperforms existing approaches

A hybrid genetic algorithm for the multi-depot vehicle routing problem

The distribution of finished products from depots to customers is a practical and challenging problem in logistics management. Better routing and scheduling decisions can result in higher level of customer satisfaction because more customers can be served in a shorter time. The distribution problem is generally formulated as the vehicle routing problem (VRP). Nevertheless, there is a rigid assumption that there is only one depot. In cases, for instance, where a logistics company has more than one depot, the VRP is not suitable. To resolve this limitation, this paper focuses on the VRP with multiple depots, or multi-depot VRP (MDVRP). The MDVRP is NP-hard, which means that an efficient algorithm for solving the problem to optimality is unavailable. To deal with the problem efficiently, two hybrid genetic algorithms (HGAs) are developed in this paper. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method and the nearest neighbor heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different problem sizes. It is proved that the performance of HGA2 is superior to that of HGA1 in terms of the total delivery time.

Optimization of PCB component placements for the collect-and-place machines

This paper presents two hybrid genetic algorithms (HGAs) to optimize the component placement operation for the collect-and-place machines in printed circuit board (PCB) assembly. The component placement problem is to optimize (i) the assignment of components to a movable revolver head or assembly tour, (ii) the sequence of component placements on a stationary PCB in each tour, and (iii) the arrangement of component types to stationary feeders simultaneously. The objective of the problem is to minimize the total traveling time spent by the revolver head for assembling all components on the PCB. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method, the nearest neighbor heuristic, and the neighborhood frequency heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different population sizes. It is proved that the performance of HGA2 is superior to HGA1 in terms of the total assembly time.

Component scheduling for chip shooter machines: a hybrid genetic algorithm approach

A chip shooter machine for electronic component assembly has a movable feeder carrier, a movable X–Y table carrying a printed circuit board (PCB), and a rotary turret with multiple assembly heads. This paper presents a hybrid genetic algorithm (HGA) to optimize the sequence of component placements and the arrangement of component types to feeders simultaneously for a chip shooter machine, that is, the component scheduling problem. The objective of the problem is to minimize the total assembly time. The GA developed in the paper hybridizes different search heuristics including the nearest-neighbor heuristic, the 2-opt heuristic, and an iterated swap procedure, which is a new improved heuristic. Compared with the results obtained by other researchers, the performance of the HGA is superior in terms of the assembly time. Scope and purpose When assembling the surface mount components on a PCB, it is necessary to obtain the optimal sequence of component placements and the best arrangement of component types to feeders simultaneously in order to minimize the total assembly time. Since it is very difficult to obtain the optimality, a GA hybridized with several search heuristics is developed. The type of machines being studied is the chip shooter machine. This paper compares the algorithm with a simple GA. It shows that the performance of the algorithm is superior to that of the simple GA in terms of the total assembly time.

A hybrid genetic algorithm for sequencing PCB component placement

A chip shooter machine for electronic components assembly has a movable feeder carrier holding components, a movable X-Y table carrying a printed circuit board (PCB), and a rotary turret having multiple assembly heads. This paper presents a hybrid genetic algorithm to optimize the sequence of component placements for a chip shooter machine. The objective of the problem is to minimize the total traveling distance of the X-Y table or the board. The genetic algorithm developed in the paper hybridizes the nearest neighbor heuristic, and an iterated swap procedure, which is a new improved heuristic. We have compared the performance of the hybrid genetic algorithm with that of the approach proposed by other researchers and have demonstrated our algorithm is superior in terms of the distance traveled by the X-Y table or the board.

A hybrid genetic algorithm for component sequencing and feeder arrangement

This paper presents a hybrid genetic algorithm to optimize the sequence of component placements on a printed circuit board and the arrangement of component types to feeders simultaneously for a pick-and-place machine with multiple stationary feeders, a fixed board table and a movable placement head. The objective of the problem is to minimize the total travelling distance, or the travelling time, of the placement head. The genetic algorithm developed in the paper hybrisizes different search heuristics including the nearest neighbor heuristic, the 2-opt heuristic, and an iterated swap procedure, which is a new improving heuristic. Compared with the results obtained by other researchers, the performance of the hybrid genetic algorithm is superior to others in terms of the distance travelled by the placement head.

Visualization of molecular fingerprints

A visualization plot of a data set of molecular data is a useful tool for gaining insight into a set of molecules. In chemoinformatics, most visualization plots are of molecular descriptors, and the statistical model most often used to produce a visualization is principal component analysis (PCA). This paper takes PCA, together with four other statistical models (NeuroScale, GTM, LTM, and LTM-LIN), and evaluates their ability to produce clustering in visualizations not of molecular descriptors but of molecular fingerprints. Two different tasks are addressed: understanding structural information (particularly combinatorial libraries) and relating structure to activity. The quality of the visualizations is compared both subjectively (by visual inspection) and objectively (with global distance comparisons and local k-nearest-neighbor predictors). On the data sets used to evaluate clustering by structure, LTM is found to perform significantly better than the other models. In particular, the clusters in LTM visualization space are consistent with the relationships between the core scaffolds that define the combinatorial sublibraries. On the data sets used to evaluate clustering by activity, LTM again gives the best performance but by a smaller margin. The results of this paper demonstrate the value of using both a nonlinear projection map and a Bernoulli noise model for modeling binary data.

Gold nanoparticles decorated with oligo(ethylene glycol) thiols:kinetics of colloid aggregation driven by depletion forces

We have studied the kinetics of the phase-separation process of mixtures of colloid and protein in solutions by real-time UV-vis spectroscopy. Complementary small-angle X-ray scattering (SAXS) was employed to determine the structures involved. The colloids used are gold nanoparticles functionalized with protein resistant oligo(ethylene glycol) (OEG) thiol, HS(CH(2))(11)(OCH(2)CH(2))(6)OMe (EG6OMe). After mixing with protein solution above a critical concentration, c*, SAXS measurements show that a scattering maximum appears after a short induction time at q = 0.0322 angstrom(-1) stop, which increases its intensity with time but the peak position does not change with time, protein concentration and salt addition. The peak corresponds to the distance of the nearest neighbor in the aggregates. The upturn of scattering intensities in the low q-range developed with time indicating the formation of aggregates. No Bragg peaks corresponding to the formation of colloidal crystallites could be observed before the clusters dropped out from the solution. The growth kinetics of aggregates is followed in detail by real-time UV-vis spectroscopy, using the flocculation parameter defined as the integral of the absorption in the range of 600-800 nm wavelengths. At low salt addition (<0.5 M), a kinetic crossover from reaction-limited cluster aggregation (RLCA) to diffusion-limited cluster aggregation (DLCA) growth model is observed, and interpreted as being due to the effective repulsive interaction barrier between colloids within the depletion potential. Above 0.5 M NaCl, the surface charge of proteins is screened significantly, and the repulsive potential barrier disappeared, thus the growth kinetics can be described by a DLCA model only.

Structural characterization of titanium-doped Bioglass using isotopic substitution neutron diffraction

Melt quenched silicate glasses containing calcium, phosphorus and alkali metals have the ability to promote bone regeneration and to fuse to living bone. Of these glasses 45S5 Bioglass® is the most widely used being sold in over 35 countries as a bone graft product for medical and dental applications; particulate 45S5 is also incorporated into toothpastes to help remineralize the surface of teeth. Recently it has been suggested that adding titanium dioxide can increase the bioactivity of these materials. This work investigates the structural consequences of incorporating 4 mol% TiO2 into Bioglass® using isotopic substitution (of the Ti) applied to neutron diffraction and X-ray Absorption Near Edge Structure (XANES). We present the first isotopic substitution data applied to melt quench derived Bioglass or its derivatives. Results show that titanium is on average surrounded by 5.2(1) nearest neighbor oxygen atoms. This implies an upper limit of 40% four-fold coordinated titanium and shows that the network connectivity is reduced from 2.11 to 1.97 for small quantities of titanium. Titanium XANES micro-fluorescence confirms the titanium environment is homogenous on the micron length scale within these glasses. Solid state magic angle spinning (MAS) NMR confirms the network connectivity model proposed. Furthermore, the results show the intermediate range order containing Na-O, Ca-O, O-P-O and O-Si-O correlations are unaffected by the addition of small quantities of TiO2 into these systems.

Glass fragility and atomic ordering on the intermediate and extended range

The relation between the fragility of glass-forming systems, a parameter which describes many of their key physical characteristics, and atomic scale structure is investigated by using neutron diffraction to measure the topological and chemical ordering for germania, or GeO2, which is an archetypal strong glass former. We find that the ordering for this and other tetrahedral network-forming glasses at distances greater than the nearest neighbor can be rationalized in terms of an interplay between the relative importance of two length scales. One of these is associated with an intermediate range, the other with an extended range and, with increasing glass fragility, it is the extended range ordering which dominates.

The risk of re-intervention after endovascular aortic aneurysm repair

This thesis studies survival analysis techniques dealing with censoring to produce predictive tools that predict the risk of endovascular aortic aneurysm repair (EVAR) re-intervention. Censoring indicates that some patients do not continue follow up, so their outcome class is unknown. Methods dealing with censoring have drawbacks and cannot handle the high censoring of the two EVAR datasets collected. Therefore, this thesis presents a new solution to high censoring by modifying an approach that was incapable of differentiating between risks groups of aortic complications. Feature selection (FS) becomes complicated with censoring. Most survival FS methods depends on Cox's model, however machine learning classifiers (MLC) are preferred. Few methods adopted MLC to perform survival FS, but they cannot be used with high censoring. This thesis proposes two FS methods which use MLC to evaluate features. The two FS methods use the new solution to deal with censoring. They combine factor analysis with greedy stepwise FS search which allows eliminated features to enter the FS process. The first FS method searches for the best neural networks' configuration and subset of features. The second approach combines support vector machines, neural networks, and K nearest neighbor classifiers using simple and weighted majority voting to construct a multiple classifier system (MCS) for improving the performance of individual classifiers. It presents a new hybrid FS process by using MCS as a wrapper method and merging it with the iterated feature ranking filter method to further reduce the features. The proposed techniques outperformed FS methods based on Cox's model such as; Akaike and Bayesian information criteria, and least absolute shrinkage and selector operator in the log-rank test's p-values, sensitivity, and concordance. This proves that the proposed techniques are more powerful in correctly predicting the risk of re-intervention. Consequently, they enable doctors to set patients’ appropriate future observation plan.

A realtime Internet-based quality control application for hurricane surface wind observations

This thesis chronicles the design and implementation of a Internet/Intranet and database based application for the quality control of hurricane surface wind observations. A quality control session consists of selecting desired observation types to be viewed and determining a storm track based time window for viewing the data. All observations of the selected types are then plotted in a storm relative view for the chosen time window and geography is positioned for the storm-center time about which an objective analysis can be performed. Users then make decisions about data validity through visual nearest-neighbor comparison and inspection. The project employed an Object Oriented iterative development method from beginning to end and its implementation primarily features the Java programming language. ^