Parallel Computer Vision Algorithms for Graphics Processing Units

La evolución de los teléfonos móviles inteligentes, dotados de cámaras digitales, está provocando una creciente demanda de aplicaciones cada vez más complejas que necesitan algoritmos de visión artificial en tiempo real; puesto que el tamaño de las señales de vídeo no hace sino aumentar y en cambio el rendimiento de los procesadores de un solo núcleo se ha estancado, los nuevos algoritmos que se diseñen para visión artificial han de ser paralelos para poder ejecutarse en múltiples procesadores y ser computacionalmente escalables. Una de las clases de procesadores más interesantes en la actualidad se encuentra en las tarjetas gráficas (GPU), que son dispositivos que ofrecen un alto grado de paralelismo, un excelente rendimiento numérico y una creciente versatilidad, lo que los hace interesantes para llevar a cabo computación científica. En esta tesis se exploran dos aplicaciones de visión artificial que revisten una gran complejidad computacional y no pueden ser ejecutadas en tiempo real empleando procesadores tradicionales. En cambio, como se demuestra en esta tesis, la paralelización de las distintas subtareas y su implementación sobre una GPU arrojan los resultados deseados de ejecución con tasas de refresco interactivas. Asimismo, se propone una técnica para la evaluación rápida de funciones de complejidad arbitraria especialmente indicada para su uso en una GPU. En primer lugar se estudia la aplicación de técnicas de síntesis de imágenes virtuales a partir de únicamente dos cámaras lejanas y no paralelas—en contraste con la configuración habitual en TV 3D de cámaras cercanas y paralelas—con información de color y profundidad. Empleando filtros de mediana modificados para la elaboración de un mapa de profundidad virtual y proyecciones inversas, se comprueba que estas técnicas son adecuadas para una libre elección del punto de vista. Además, se demuestra que la codificación de la información de profundidad con respecto a un sistema de referencia global es sumamente perjudicial y debería ser evitada. Por otro lado se propone un sistema de detección de objetos móviles basado en técnicas de estimación de densidad con funciones locales. Este tipo de técnicas es muy adecuada para el modelado de escenas complejas con fondos multimodales, pero ha recibido poco uso debido a su gran complejidad computacional. El sistema propuesto, implementado en tiempo real sobre una GPU, incluye propuestas para la estimación dinámica de los anchos de banda de las funciones locales, actualización selectiva del modelo de fondo, actualización de la posición de las muestras de referencia del modelo de primer plano empleando un filtro de partículas multirregión y selección automática de regiones de interés para reducir el coste computacional. Los resultados, evaluados sobre diversas bases de datos y comparados con otros algoritmos del estado del arte, demuestran la gran versatilidad y calidad de la propuesta. Finalmente se propone un método para la aproximación de funciones arbitrarias empleando funciones continuas lineales a tramos, especialmente indicada para su implementación en una GPU mediante el uso de las unidades de filtraje de texturas, normalmente no utilizadas para cómputo numérico. La propuesta incluye un riguroso análisis matemático del error cometido en la aproximación en función del número de muestras empleadas, así como un método para la obtención de una partición cuasióptima del dominio de la función para minimizar el error. ABSTRACT The evolution of smartphones, all equipped with digital cameras, is driving a growing demand for ever more complex applications that need to rely on real-time computer vision algorithms. However, video signals are only increasing in size, whereas the performance of single-core processors has somewhat stagnated in the past few years. Consequently, new computer vision algorithms will need to be parallel to run on multiple processors and be computationally scalable. One of the most promising classes of processors nowadays can be found in graphics processing units (GPU). These are devices offering a high parallelism degree, excellent numerical performance and increasing versatility, which makes them interesting to run scientific computations. In this thesis, we explore two computer vision applications with a high computational complexity that precludes them from running in real time on traditional uniprocessors. However, we show that by parallelizing subtasks and implementing them on a GPU, both applications attain their goals of running at interactive frame rates. In addition, we propose a technique for fast evaluation of arbitrarily complex functions, specially designed for GPU implementation. First, we explore the application of depth-image–based rendering techniques to the unusual configuration of two convergent, wide baseline cameras, in contrast to the usual configuration used in 3D TV, which are narrow baseline, parallel cameras. By using a backward mapping approach with a depth inpainting scheme based on median filters, we show that these techniques are adequate for free viewpoint video applications. In addition, we show that referring depth information to a global reference system is ill-advised and should be avoided. Then, we propose a background subtraction system based on kernel density estimation techniques. These techniques are very adequate for modelling complex scenes featuring multimodal backgrounds, but have not been so popular due to their huge computational and memory complexity. The proposed system, implemented in real time on a GPU, features novel proposals for dynamic kernel bandwidth estimation for the background model, selective update of the background model, update of the position of reference samples of the foreground model using a multi-region particle filter, and automatic selection of regions of interest to reduce computational cost. The results, evaluated on several databases and compared to other state-of-the-art algorithms, demonstrate the high quality and versatility of our proposal. Finally, we propose a general method for the approximation of arbitrarily complex functions using continuous piecewise linear functions, specially formulated for GPU implementation by leveraging their texture filtering units, normally unused for numerical computation. Our proposal features a rigorous mathematical analysis of the approximation error in function of the number of samples, as well as a method to obtain a suboptimal partition of the domain of the function to minimize approximation error.

Oligomerization domain-directed reassembly of active dihydrofolate reductase from rationally designed fragments

Reassembly of enzymes from peptide fragments has been used as a strategy for understanding the evolution, folding, and role of individual subdomains in catalysis and regulation of activity. We demonstrate an oligomerization-assisted enzyme reassembly strategy whereby fragments are covalently linked to independently folding and interacting domains whose interactions serve to promote efficient refolding and complementation of fragments, forming active enzyme. We show that active murine dihydrofolate reductase (E.C. 1.5.1.3) can be reassembled from complementary N- and C-terminal fragments when fused to homodimerizing GCN4 leucine zipper-forming sequences as well as heterodimerizing protein partners. Reassembly is detected by an in vivo selection assay in Escherichia coli and in vitro. The effects of mutations that disrupt fragment affinity or enzyme activity were assessed. The steady–state kinetic parameters for the reassembled mutant (Phe-31 → Ser) were determined; they are not significantly different from the full-length mutant. The strategy described here provides a general approach for protein dissection and domain swapping studies, with the capacity both for rapid in vivo screening as well as in vitro characterization. Further, the strategy suggests a simple in vivo enzyme-based detection system for protein–protein interactions, which we illustrate with two examples: ras–GTPase and raf–ras-binding domain and FK506-binding protein-rapamycin complexed with the target of rapamycin TOR2.

DNA packing in stable lipid complexes designed for gene transfer imitates DNA compaction in bacteriophage

The structure of complexes made from DNA and suitable lipids (lipoplex, Lx) was examined by cryo-electron microscopy (cryoEM). We observed a distinct concentric ring-like pattern with striated shells when using plasmid DNA. These spherical multilamellar particles have a mean diameter of 254 nm with repetitive spacing of 7.5 nm with striation of 5.3 nm width. Small angle x-ray scattering revealed repetitive ordering of 6.9 nm, suggesting a lamellar structure containing at least 12 layers. This concentric and lamellar structure with different packing regimes also was observed by cryoEM when using linear double-stranded DNA, single-stranded DNA, and oligodeoxynucleotides. DNA chains could be visualized in DNA/lipid complexes. Such specific supramolecular organization is the result of thermodynamic forces, which cause compaction to occur through concentric winding of DNA in a liquid crystalline phase. CryoEM examination of T4 phage DNA packed either in T4 capsides or in lipidic particles showed similar patterns. Small angle x-ray scattering suggested an hexagonal phase in Lx-T4 DNA. Our results indicate that both lamellar and hexagonal phases may coexist in the same Lx preparation or particle and that transition between both phases may depend on equilibrium influenced by type and length of the DNA used.

Sustained in vivo cardiac protection by a rationally designed peptide that causes ɛ protein kinase C translocation

Brief periods of cardiac ischemia trigger protection from subsequent prolonged ischemia (preconditioning). ɛ Protein kinase C (ɛPKC) has been suggested to mediate preconditioning. Here, we describe an ɛPKC-selective agonist octapeptide, ψɛ receptor for activated C-kinase (ψɛRACK), derived from an ɛPKC sequence homologous to its anchoring protein, ɛRACK. Introduction of ψɛRACK into isolated cardiomyocytes, or its postnatal expression as a transgene in mouse hearts, increased ɛPKC translocation and caused cardio-protection from ischemia without any deleterious effects. Our data demonstrate that ɛPKC activation is required for protection from ischemic insult and suggest that small molecules that mimic this ɛPKC agonist octapeptide provide a powerful therapeutic approach to protect hearts at risk for ischemia.

Folding and aggregation of designed proteins

Protein aggregation is studied by following the simultaneous folding of two designed identical 20-letter amino acid chains within the framework of a lattice model and using Monte Carlo simulations. It is found that protein aggregation is determined by elementary structures (partially folded intermediates) controlled by local contacts among some of the most strongly interacting amino acids and formed at an early stage in the folding process.

Investigation of the mechanisms of DNA binding of the human G/T glycosylase using designed inhibitors

Deamination of 5-methylcytosine residues in DNA gives rise to the G/T mismatched base pair. In humans this lesion is repaired by a mismatch-specific thymine DNA glycosylase (TDG or G/T glycosylase), which catalyzes specific excision of the thymine base through N-glycosidic bond hydrolysis. Unlike other DNA glycosylases, TDG recognizes an aberrant pairing of two normal bases rather than a damaged base per se. An important structural issue is thus to understand how the enzyme specifically targets the T (or U) residue of the mismatched base pair. Our approach toward the study of substrate recognition and processing by catalytic DNA binding proteins has been to modify the substrate so as to preserve recognition of the base but to prevent its excision. Here we report that replacement of 2′-hydrogen atoms with fluorine in the substrate 2′-deoxyguridine (dU) residue abrogates glycosidic bond cleavage, thereby leading to the formation of a tight, specific glycosylase–DNA complex. Biochemical characterization of these complexes reveals that the enzyme protects an ≈20-bp stretch of the substrate from DNase I cleavage, and directly contacts a G residue on the 3′ side of the mismatched U derivative. These studies provide a mechanistic rationale for the preferential repair of deaminated CpG sites and pave the way for future high-resolution studies of TDG bound to DNA.

Positive and negative regulation of endogenous genes by designed transcription factors

Gene regulation by imposed localization was studied by using designed zinc finger proteins that bind 18-bp DNA sequences in the 5′ untranslated regions of the protooncogenes erbB-2 and erbB-3. Transcription factors were generated by fusion of the DNA-binding proteins to repression or activation domains. When introduced into cells these transcription factors acted as dominant repressors or activators of, respectively, endogenous erbB-2 or erbB-3 gene expression. Significantly, imposed regulation of the two genes was highly specific, despite the fact that the transcription factor binding sites targeted in erbB-2 and erbB-3 share 15 of 18 nucleotides. Regulation of erbB-2 gene expression was observed in cells derived from several species that conserve the DNA target sequence. Repression of erbB-2 in SKBR3 breast cancer cells inhibited cell-cycle progression by inducing a G1 accumulation, suggesting the potential of designed transcription factors for cancer gene therapy. These results demonstrate the willful up- and down-regulation of endogenous genes, and provide an additional means to alter biological systems.

A computationally directed screen identifying interacting coiled coils from Saccharomyces cerevisiae

Computational methods can frequently identify protein-interaction motifs in otherwise uncharacterized open reading frames. However, the identification of candidate ligands for these motifs (e.g., so that partnering can be determined experimentally in a directed manner) is often beyond the scope of current computational capabilities. One exception is provided by the coiled-coil interaction motif, which consists of two or more α helices that wrap around each other: the ligands for coiled-coil sequences are generally other coiled-coil sequences, thereby greatly simplifying the motif/ligand recognition problem. Here, we describe a two-step approach to identifying protein–protein interactions mediated by two-stranded coiled coils that occur in Saccharomyces cerevisiae. Coiled coils from the yeast genome are first predicted computationally, by using the multicoil program, and associations between coiled coils are then determined experimentally by using the yeast two-hybrid assay. We report 213 unique interactions between 162 putative coiled-coil sequences. We evaluate the resulting interactions, focusing on associations identified between components of the spindle pole body (the yeast centrosome).

Designed protein tetramer zipped together with a hydrophobic Alzheimer homology: A structural clue to amyloid assembly

Limited solubility and precipitation of amyloidogenic sequences such as the Alzheimer peptide (β-AP) are major obstacles to a molecular understanding of protein fibrillation and deposition processes. Here we have circumvented the solubility problem by stepwise engineering a β-AP homology into a soluble scaffold, the monomeric protein S6. The S6 construct with the highest β-AP homology crystallizes as a tetramer that is linked by the β-AP residues forming intermolecular antiparallel β-sheets. This construct also shows increased coil aggregation during refolding, and a 14-mer peptide encompassing the engineered sequence forms fibrils. Mutational analysis shows that intermolecular association is linked to the overall hydrophobicity of the sticky sequence and implies the existence of “structural gatekeepers” in the wild-type protein, that is, charged side chains that prevent aggregation by interrupting contiguous stretches of hydrophobic residues in the primary sequence.

Using three-dimensional microfluidic networks for solving computationally hard problems

This paper describes the design of a parallel algorithm that uses moving fluids in a three-dimensional microfluidic system to solve a nondeterministically polynomial complete problem (the maximal clique problem) in polynomial time. This algorithm relies on (i) parallel fabrication of the microfluidic system, (ii) parallel searching of all potential solutions by using fluid flow, and (iii) parallel optical readout of all solutions. This algorithm was implemented to solve the maximal clique problem for a simple graph with six vertices. The successful implementation of this algorithm to compute solutions for small-size graphs with fluids in microchannels is not useful, per se, but does suggest broader application for microfluidics in computation and control.

Self-assembled monolayers from a designed combinatorial library of de novo β-sheet proteins

A variety of naturally occurring biomaterials owe their unusual structural and mechanical properties to layers of β-sheet proteins laminated between layers of inorganic mineral. To explore the possibility of fabricating novel two-dimensional protein layers, we studied the self-assembly properties of de novo proteins from a designed combinatorial library. Each protein in the library has a distinct 63 amino acid sequence, yet they all share an identical binary pattern of polar and nonpolar residues, which was designed to favor the formation of six-stranded amphiphilic β-sheets. Characterization of proteins isolated from the library demonstrates that (i) they self assemble into monolayers at an air/water interface; (ii) the monolayers are dominated by β-sheet secondary structure, as shown by both circular dichroism and infrared spectroscopies; and (iii) the measured areas (500- 600 Å2) of individual protein molecules in the monolayers match those expected for proteins folded into amphiphilic β-sheets. The finding that similar structures are formed by distinctly different protein sequences suggests that assembly into β-sheet monolayers can be encoded by binary patterning of polar and nonpolar amino acids. Moreover, because the designed binary pattern is compatible with a wide variety of different sequences, it may be possible to fabricate β-sheet monolayers by using combinations of side chains that are explicitly designed to favor particular applications of novel biomaterials.

Profilin Binding to Poly-l-Proline and Actin Monomers along with Ability to Catalyze Actin Nucleotide Exchange Is Required for Viability of Fission Yeast

We tested the ability of 87 profilin point mutations to complement temperature-sensitive and null mutations of the single profilin gene of the fission yeast Schizosaccharomyces pombe. We compared the biochemical properties of 13 stable noncomplementing profilins with an equal number of complementing profilin mutants. A large quantitative database revealed the following: 1) in a profilin null background fission yeast grow normally with profilin mutations having >10% of wild-type affinity for actin or poly-l-proline, but lower affinity for either ligand is incompatible with life; 2) in the cdc3-124 profilin ts background, fission yeast function with profilin having only 2–5% wild-type affinity for actin or poly-l-proline; and 3) special mutations show that the ability of profilin to catalyze nucleotide exchange by actin is an essential function. Thus, poly-l-proline binding, actin binding, and actin nucleotide exchange are each independent requirements for profilin function in fission yeast.

Cutin Monomers and Surface Wax Constituents Elicit H2O2 in Conditioned Cucumber Hypocotyl Segments and Enhance the Activity of Other H2O2 Elicitors1

Hypocotyls from etiolated cucumber (Cucumis sativus L.) seedlings were gently abraded at their epidermal surface and cut segments were conditioned to develop competence for H2O2 elicitation. Alkaline hydrolysates of cutin from cucumber, tomato, and apple elicited H2O2 in such conditioned segments. The most active constituent of cucumber cutin was identified as dodecan-1-ol, a novel cutin monomer capable of forming hydrophobic terminal chains. Additionally, the cutin hydrolysates enhanced the activity of a fungal H2O2 elicitor, similar to cucumber surface wax, which contained newly identified alkan-1,3-diols. The specificity of elicitor and enhancement activity was further elaborated using some pure model compounds. Certain saturated hydroxy fatty acids were potent H2O2 elicitors as well as enhancers. Some unsaturated epoxy and hydroxy fatty acids were also excellent H2O2 elicitors but inhibited the fungal elicitor activity. Short-chain alkanols exhibited good elicitor and enhancer activity, whereas longer-chain alkan-1-ols were barely active. The enhancement effect was also observed for H2O2 elicitation by ergosterol and chitosan. The physiological significance of these observations might be that once the cuticle is degraded by fungal cutinase, the cutin monomers may act as H2O2 elicitors. Corrosion of cutin may also bring surface wax constituents in contact with protoplasts and enhance elicitation.

On the failure of de novo-designed peptides as biocatalysts.

While the elegance and efficiency of enzymatic catalysis have long tempted chemists and biochemists with reductionist leanings to try to mimic the functions of natural enzymes in much smaller peptides, such efforts have only rarely produced catalysts with biologically interesting properties. However, the advent of genetic engineering and hybridoma technology and the discovery of catalytic RNA have led to new and very promising alternative means of biocatalyst development. Synthetic chemists have also had some success in creating nonpeptide catalysts with certain enzyme-like characteristics, although their rates and specificities are generally much poorer than those exhibited by the best novel biocatalysts based on natural structures. A comparison of the various approaches from theoretical and practical viewpoints is presented. It is suggested that, given our current level of understanding, the most fruitful methods may incorporate both iterative selection strategies and rationally chosen small perturbations, superimposed on frameworks designed by nature.

Targeting nucleic acid secondary structures by antisense oligonucleotides designed through in vitro selection.

Using an in vitro selection approach, we have isolated oligonucleotides that can bind to a DNA hairpin structure. Complex formation of these oligonucleotides with the target hairpin involves some type of triple-stranded structure with noncanonical interaction, as indicated by bandshift assays and footprinting studies. The selected oligomers can block restriction endonuclease cleavage of the target hairpin in a sequence-specific manner. We demonstrate that in vitro selection can extend the antisense approach to functional targeting of secondary structure motifs. This could provide a basis for interfering with regulatory processes mediated by a variety of nucleic acid structures.