Index Trees for Efficient Deformable Shape-based Retrieval

An improved method for deformable shape-based image indexing and retrieval is described. A pre-computed index tree is used to improve the speed of our previously reported on-line model fitting method; simple shape features are used as keys in a pre-generated index tree of model instances. In addition, a coarse to fine indexing scheme is used at different levels of the tree to further improve speed while maintaining matching accuracy. Experimental results show that the speedup is significant, while accuracy of shape-based indexing is maintained. A method for shape population-based retrieval is also described. The method allows query formulation based on the population distributions of shapes in each image. Results of population-based image queries for a database of blood cell micrographs are shown.

MosaicShape: Stochastic Region Grouping with Shape Prior

A novel method that combines shape-based object recognition and image segmentation is proposed for shape retrieval from images. Given a shape prior represented in a multi-scale curvature form, the proposed method identifies the target objects in images by grouping oversegmented image regions. The problem is formulated in a unified probabilistic framework and solved by a stochastic Markov Chain Monte Carlo (MCMC) mechanism. By this means, object segmentation and recognition are accomplished simultaneously. Within each sampling move during the simulation process,probabilistic region grouping operations are influenced by both the image information and the shape similarity constraint. The latter constraint is measured by a partial shape matching process. A generalized parallel algorithm by Barbu and Zhu,combined with a large sampling jump and other implementation improvements, greatly speeds up the overall stochastic process. The proposed method supports the segmentation and recognition of multiple occluded objects in images. Experimental results are provided for both synthetic and real images.

Robust Sketching and Aggregation of Distributed Data Streams

The data streaming model provides an attractive framework for one-pass summarization of massive data sets at a single observation point. However, in an environment where multiple data streams arrive at a set of distributed observation points, sketches must be computed remotely and then must be aggregated through a hierarchy before queries may be conducted. As a result, many sketch-based methods for the single stream case do not apply directly, as either the error introduced becomes large, or because the methods assume that the streams are non-overlapping. These limitations hinder the application of these techniques to practical problems in network traffic monitoring and aggregation in sensor networks. To address this, we develop a general framework for evaluating and enabling robust computation of duplicate-sensitive aggregate functions (e.g., SUM and QUANTILE), over data produced by distributed sources. We instantiate our approach by augmenting the Count-Min and Quantile-Digest sketches to apply in this distributed setting, and analyze their performance. We conclude with experimental evaluation to validate our analysis.

Detecting Instances of Shape Classes That Exhibit Variable Structure

This paper proposes a method for detecting shapes of variable structure in images with clutter. The term "variable structure" means that some shape parts can be repeated an arbitrary number of times, some parts can be optional, and some parts can have several alternative appearances. The particular variation of the shape structure that occurs in a given image is not known a priori. Existing computer vision methods, including deformable model methods, were not designed to detect shapes of variable structure; they may only be used to detect shapes that can be decomposed into a fixed, a priori known, number of parts. The proposed method can handle both variations in shape structure and variations in the appearance of individual shape parts. A new class of shape models is introduced, called Hidden State Shape Models, that can naturally represent shapes of variable structure. A detection algorithm is described that finds instances of such shapes in images with large amounts of clutter by finding globally optimal correspondences between image features and shape models. Experiments with real images demonstrate that our method can localize plant branches that consist of an a priori unknown number of leaves and can detect hands more accurately than a hand detector based on the chamfer distance.

Learning Embeddings for Indexing, Retrieval, and Classification, with Applications to Object and Shape Recognition in Image Databases

Nearest neighbor retrieval is the task of identifying, given a database of objects and a query object, the objects in the database that are the most similar to the query. Retrieving nearest neighbors is a necessary component of many practical applications, in fields as diverse as computer vision, pattern recognition, multimedia databases, bioinformatics, and computer networks. At the same time, finding nearest neighbors accurately and efficiently can be challenging, especially when the database contains a large number of objects, and when the underlying distance measure is computationally expensive. This thesis proposes new methods for improving the efficiency and accuracy of nearest neighbor retrieval and classification in spaces with computationally expensive distance measures. The proposed methods are domain-independent, and can be applied in arbitrary spaces, including non-Euclidean and non-metric spaces. In this thesis particular emphasis is given to computer vision applications related to object and shape recognition, where expensive non-Euclidean distance measures are often needed to achieve high accuracy. The first contribution of this thesis is the BoostMap algorithm for embedding arbitrary spaces into a vector space with a computationally efficient distance measure. Using this approach, an approximate set of nearest neighbors can be retrieved efficiently - often orders of magnitude faster than retrieval using the exact distance measure in the original space. The BoostMap algorithm has two key distinguishing features with respect to existing embedding methods. First, embedding construction explicitly maximizes the amount of nearest neighbor information preserved by the embedding. Second, embedding construction is treated as a machine learning problem, in contrast to existing methods that are based on geometric considerations. The second contribution is a method for constructing query-sensitive distance measures for the purposes of nearest neighbor retrieval and classification. In high-dimensional spaces, query-sensitive distance measures allow for automatic selection of the dimensions that are the most informative for each specific query object. It is shown theoretically and experimentally that query-sensitivity increases the modeling power of embeddings, allowing embeddings to capture a larger amount of the nearest neighbor structure of the original space. The third contribution is a method for speeding up nearest neighbor classification by combining multiple embedding-based nearest neighbor classifiers in a cascade. In a cascade, computationally efficient classifiers are used to quickly classify easy cases, and classifiers that are more computationally expensive and also more accurate are only applied to objects that are harder to classify. An interesting property of the proposed cascade method is that, under certain conditions, classification time actually decreases as the size of the database increases, a behavior that is in stark contrast to the behavior of typical nearest neighbor classification systems. The proposed methods are evaluated experimentally in several different applications: hand shape recognition, off-line character recognition, online character recognition, and efficient retrieval of time series. In all datasets, the proposed methods lead to significant improvements in accuracy and efficiency compared to existing state-of-the-art methods. In some datasets, the general-purpose methods introduced in this thesis even outperform domain-specific methods that have been custom-designed for such datasets.

Authenticated Index Structures for Aggregation Queries in Outsourced Databases

In an outsourced database system the data owner publishes information through a number of remote, untrusted servers with the goal of enabling clients to access and query the data more efficiently. As clients cannot trust servers, query authentication is an essential component in any outsourced database system. Clients should be given the capability to verify that the answers provided by the servers are correct with respect to the actual data published by the owner. While existing work provides authentication techniques for selection and projection queries, there is a lack of techniques for authenticating aggregation queries. This article introduces the first known authenticated index structures for aggregation queries. First, we design an index that features good performance characteristics for static environments, where few or no updates occur to the data. Then, we extend these ideas and propose more involved structures for the dynamic case, where the database owner is allowed to update the data arbitrarily. Our structures feature excellent average case performance for authenticating queries with multiple aggregate attributes and multiple selection predicates. We also implement working prototypes of the proposed techniques and experimentally validate the correctness of our ideas.

Object Detection at the Optimal Scale with Hidden State Shape Models

Hidden State Shape Models (HSSMs) [2], a variant of Hidden Markov Models (HMMs) [9], were proposed to detect shape classes of variable structure in cluttered images. In this paper, we formulate a probabilistic framework for HSSMs which provides two major improvements in comparison to the previous method [2]. First, while the method in [2] required the scale of the object to be passed as an input, the method proposed here estimates the scale of the object automatically. This is achieved by introducing a new term for the observation probability that is based on a object-clutter feature model. Second, a segmental HMM [6, 8] is applied to model the "duration probability" of each HMM state, which is learned from the shape statistics in a training set and helps obtain meaningful registration results. Using a segmental HMM provides a principled way to model dependencies between the scales of different parts of the object. In object localization experiments on a dataset of real hand images, the proposed method significantly outperforms the method of [2], reducing the incorrect localization rate from 40% to 15%. The improvement in accuracy becomes more significant if we consider that the method proposed here is scale-independent, whereas the method of [2] takes as input the scale of the object we want to localize.

Intersubject Regularity in the Intrinsic Shape of Human V1

Previous studies have reported considerable intersubject variability in the three-dimensional geometry of the human primary visual cortex (V1). Here we demonstrate that much of this variability is due to extrinsic geometric features of the cortical folds, and that the intrinsic shape of V1 is similar across individuals. V1 was imaged in ten ex vivo human hemispheres using high-resolution (200 μm) structural magnetic resonance imaging at high field strength (7 T). Manual tracings of the stria of Gennari were used to construct a surface representation, which was computationally flattened into the plane with minimal metric distortion. The instrinsic shape of V1 was determined from the boundary of the planar representation of the stria. An ellipse provided a simple parametric shape model that was a good approximation to the boundary of flattened V1. The aspect ration of the best-fitting ellipse was found to be consistent across subject, with a mean of 1.85 and standard deviation of 0.12. Optimal rigid alignment of size-normalized V1 produced greater overlap than that achieved by previous studies using different registration methods. A shape analysis of published macaque data indicated that the intrinsic shape of macaque V1 is also stereotyped, and similar to the human V1 shape. Previoud measurements of the functional boundary of V1 in human and macaque are in close agreement with these results.

A Neural Model of 3D Shape-From-Texture: Multiple-Scale Filtering, Boundary Grouping, and Surface Filling-In

A neural model is presented of how cortical areas V1, V2, and V4 interact to convert a textured 2D image into a representation of curved 3D shape. Two basic problems are solved to achieve this: (1) Patterns of spatially discrete 2D texture elements are transformed into a spatially smooth surface representation of 3D shape. (2) Changes in the statistical properties of texture elements across space induce the perceived 3D shape of this surface representation. This is achieved in the model through multiple-scale filtering of a 2D image, followed by a cooperative-competitive grouping network that coherently binds texture elements into boundary webs at the appropriate depths using a scale-to-depth map and a subsequent depth competition stage. These boundary webs then gate filling-in of surface lightness signals in order to form a smooth 3D surface percept. The model quantitatively simulates challenging psychophysical data about perception of prolate ellipsoids (Todd and Akerstrom, 1987, J. Exp. Psych., 13, 242). In particular, the model represents a high degree of 3D curvature for a certain class of images, all of whose texture elements have the same degree of optical compression, in accordance with percepts of human observers. Simulations of 3D percepts of an elliptical cylinder, a slanted plane, and a photo of a golf ball are also presented.

Effect of solder volume on joint shape with variable chip-to-board contact pad ratio

The objective of this paper is to investigate the effect of the pad size ratio between the chip and board end of a solder joint on the shape of that solder joint in combination with the solder volume available. The shape of the solder joint is correlated to its reliability and thus of importance. For low density chip bond pad applications Flip Chip (FC) manufacturing costs can be kept down by using larger size board pads suitable for solder application. By using “Surface Evolver” software package the solder joint shapes associated with different size/shape solder preforms and chip/board pad ratios are predicted. In this case a so called Flip-Chip Over Hole (FCOH) assembly format has been used. Assembly trials involved the deposition of lead-free 99.3Sn0.7Cu solder on the board side, followed by reflow, an underfill process and back die encapsulation. During the assembly work pad off-sets occurred that have been taken into account for the Surface Evolver solder joint shape prediction and accurately matched the real assembly. Overall, good correlation was found between the simulated solder joint shape and the actual fabricated solder joint shapes. Solder preforms were found to exhibit better control over the solder volume. Reflow simulation of commercially available solder preform volumes suggests that for a fixed stand-off height and chip-board pad ratio, the solder volume value and the surface tension determines the shape of the joint.

Investigation of the shape of the R(0) absorption line in ν3, N2O recorded from an axisymmetric supersonic free jet expansion

The hydrodynamic structure of an axisymmetric supersonic expansion can be regarded as a series of concentric divergent cones, with decreasing particle densities as the cone angle increases. Different groups of molecules therefore contribute to high-resolution absorption line shapes when optically probing the expansion in a direction perpendicular to the jet axis. These groups are distinguished by the cone angle, inducing a specific Doppler shift, and by the particle density, contributing a specific weight to the absorption intensity. As a result different broader line profiles are observed compared to room temperature spectra. This effect is investigated here selecting as the working example the R(0), ν3 absorption line in N2O recorded using a Fourier transform interferometer. Independent impact pressure and quadrupole mass spectrometric measurements are performed leading to two complementary maps of the expansion, allowing the recorded absorption line shape to be quantitatively modeled. © 2006 Elsevier Ltd. All rights reserved.

Platinum nuclei: Concealed configuration mixing and shape coexistence

The role of configuration mixing in the Pt region is investigated. For this chain of isotopes, the nature of the ground state changes smoothly, being spherical around mass A~174 and A~192 and deformed around the midshell N=104 region. This has a dramatic effect on the systematics of the energy spectra as compared to the systematics in the Pb and Hg nuclei. Interacting boson model with configuration mixing calculations are presented for gyromagnetic factors, α-decay hindrance factors, and isotope shifts. The necessity of incorporating intruder configurations to obtain an accurate description of the latter properties becomes evident. © 2011 American Physical Society.

A prochelator activated by beta-secretase inhibits Abeta aggregation and suppresses copper-induced reactive oxygen species formation.

The intersection of the amyloid cascade hypothesis and the implication of metal ions in Alzheimer's disease progression has sparked an interest in using metal-binding compounds as potential therapeutic agents. In the present work, we describe a prochelator SWH that is enzymatically activated by beta-secretase to produce a high affinity copper chelator CP. Because beta-secretase is responsible for the amyloidogenic processing of the amyloid precursor protein, this prochelator strategy imparts disease specificity toward copper chelation not possible with general metal chelators. Furthermore, once activated, CP efficiently sequesters copper from amyloid-beta, prevents and disassembles copper-induced amyloid-beta aggregation, and diminishes copper-promoted reactive oxygen species formation.

Hippocampus shape analysis and late-life depression.

Major depression in the elderly is associated with brain structural changes and vascular lesions. Changes in the subcortical regions of the limbic system have also been noted. Studies examining hippocampus volumetric differences in depression have shown variable results, possibly due to any volume differences being secondary to local shape changes rather than differences in the overall volume. Shape analysis offers the potential to detect such changes. The present study applied spherical harmonic (SPHARM) shape analysis to the left and right hippocampi of 61 elderly subjects with major depression and 43 non-depressed elderly subjects. Statistical models controlling for age, sex, and total cerebral volume showed a significant reduction in depressed compared with control subjects in the left hippocampus (F(1,103) = 5.26; p = 0.0240) but not right hippocampus volume (F(1,103) = 0.41; p = 0.5213). Shape analysis showed significant differences in the mid-body of the left (but not the right) hippocampus between depressed and controls. When the depressed group was dichotomized into those whose depression was remitted at time of imaging and those who were unremitted, the shape comparison showed remitted subjects to be indistinguishable from controls (both sides) while the unremitted subjects differed in the midbody and the lateral side near the head. Hippocampal volume showed no difference between controls and remitted subjects but nonremitted subjects had significantly smaller left hippocampal volumes with no significant group differences in the right hippocampus. These findings may provide support to other reports of neurogenic effects of antidepressants and their relation to successful treatment for depressive symptoms.

Construction of invisibility cloaks of arbitrary shape and size using planar layers of metamaterials

Transformation optics (TO) is a powerful tool for the design of electromagnetic and optical devices with novel functionality derived from the unusual properties of the transformation media. In general, the fabrication of TO media is challenging, requiring spatially varying material properties with both anisotropic electric and magnetic responses. Though metamaterials have been proposed as a path for achieving such complex media, the required properties arising from the most general transformations remain elusive, and cannot implemented by state-of-the-art fabrication techniques. Here, we propose faceted approximations of TO media of arbitrary shape in which the volume of the TO device is divided into flat metamaterial layers. These layers can be readily implemented by standard fabrication and stacking techniques. We illustrate our approximation approach for the specific example of a two-dimensional, omnidirectional "invisibility cloak", and quantify its performance using the total scattering cross section as a practical figure of merit. © 2012 American Institute of Physics.