Texture analysis using graphs generated by deterministic partially self-avoiding walks

Texture is one of the most important visual attributes for image analysis. It has been widely used in image analysis and pattern recognition. A partially self-avoiding deterministic walk has recently been proposed as an approach for texture analysis with promising results. This approach uses walkers (called tourists) to exploit the gray scale image contexts in several levels. Here, we present an approach to generate graphs out of the trajectories produced by the tourist walks. The generated graphs embody important characteristics related to tourist transitivity in the image. Computed from these graphs, the statistical position (degree mean) and dispersion (entropy of two vertices with the same degree) measures are used as texture descriptors. A comparison with traditional texture analysis methods is performed to illustrate the high performance of this novel approach. (C) 2011 Elsevier Ltd. All rights reserved.

Crossover between the extended and localized regimes in stochastic partially self-avoiding walks in one-dimensional disordered systems

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Dynamic texture segmentation based on deterministic partially self-avoiding walks

Recently there has been a considerable interest in dynamic textures due to the explosive growth of multimedia databases. In addition, dynamic texture appears in a wide range of videos, which makes it very important in applications concerning to model physical phenomena. Thus, dynamic textures have emerged as a new field of investigation that extends the static or spatial textures to the spatio-temporal domain. In this paper, we propose a novel approach for dynamic texture segmentation based on automata theory and k-means algorithm. In this approach, a feature vector is extracted for each pixel by applying deterministic partially self-avoiding walks on three orthogonal planes of the video. Then, these feature vectors are clustered by the well-known k-means algorithm. Although the k-means algorithm has shown interesting results, it only ensures its convergence to a local minimum, which affects the final result of segmentation. In order to overcome this drawback, we compare six methods of initialization of the k-means. The experimental results have demonstrated the effectiveness of our proposed approach compared to the state-of-the-art segmentation methods.

Dynamic texture analysis and segmentation using deterministic partially self-avoiding walks

Dynamic texture is a recent field of investigation that has received growing attention from computer vision community in the last years. These patterns are moving texture in which the concept of selfsimilarity for static textures is extended to the spatiotemporal domain. In this paper, we propose a novel approach for dynamic texture representation, that can be used for both texture analysis and segmentation. In this method, deterministic partially self-avoiding walks are performed in three orthogonal planes of the video in order to combine appearance and motion features. We validate our method on three applications of dynamic texture that present interesting challenges: recognition, clustering and segmentation. Experimental results on these applications indicate that the proposed method improves the dynamic texture representation compared to the state of the art.

Self-Avoiding Walks in the Plane

Румен Руменов Данговски, Калина Христова Петрова - Разглеждаме броя на несамопресичащите се разходки с фиксирана дължина върху целочислената решетка. Завършваме анализа върху случая за лента, с дължина едно. Чрез комбинаторни аргументи получаваме точна формула за броя на разходките върху лента, ограничена отляво и отдясно. Формулата я изследваме и асимптотично.

Complex network classification using partially self-avoiding deterministic walks

Complex networks have attracted increasing interest from various fields of science. It has been demonstrated that each complex network model presents specific topological structures which characterize its connectivity and dynamics. Complex network classification relies on the use of representative measurements that describe topological structures. Although there are a large number of measurements, most of them are correlated. To overcome this limitation, this paper presents a new measurement for complex network classification based on partially self-avoiding walks. We validate the measurement on a data set composed by 40000 complex networks of four well-known models. Our results indicate that the proposed measurement improves correct classification of networks compared to the traditional ones. (C) 2012 American Institute of Physics. [http://dx.doi.org/10.1063/1.4737515]

Ergodic crossover in partially self-avoiding stochastic walks

Consider a one-dimensional environment with N randomly distributed sites. An agent explores this random medium moving deterministically with a spatial memory μ. A crossover from local to global exploration occurs in one dimension at a well-defined memory value μ1=log2N. In its stochastic version, the dynamics is ruled by the memory and by temperature T, which affects the hopping displacement. This dynamics also shows a crossover in one dimension, obtained computationally, between exploration schemes, characterized yet by the trajectory size (Np) (aging effect). In this paper we provide an analytical approach considering the modified stochastic version where the parameter T plays the role of a maximum hopping distance. This modification allows us to obtain a general analytical expression for the crossover, as a function of the parameters μ, T, and Np. Differently from what has been proposed by previous studies, we find that the crossover occurs in any dimension d. These results have been validated by numerical experiments and may be of great value for fixing optimal parameters in search algorithms. © 2013 American Physical Society.

Texture descriptor based on partially self-avoiding deterministic walker on networks

Texture image analysis is an important field of investigation that has attracted the attention from computer vision community in the last decades. In this paper, a novel approach for texture image analysis is proposed by using a combination of graph theory and partially self-avoiding deterministic walks. From the image, we build a regular graph where each vertex represents a pixel and it is connected to neighboring pixels (pixels whose spatial distance is less than a given radius). Transformations on the regular graph are applied to emphasize different image features. To characterize the transformed graphs, partially self-avoiding deterministic walks are performed to compose the feature vector. Experimental results on three databases indicate that the proposed method significantly improves correct classification rate compared to the state-of-the-art, e.g. from 89.37% (original tourist walk) to 94.32% on the Brodatz database, from 84.86% (Gabor filter) to 85.07% on the Vistex database and from 92.60% (original tourist walk) to 98.00% on the plant leaves database. In view of these results, it is expected that this method could provide good results in other applications such as texture synthesis and texture segmentation. (C) 2012 Elsevier Ltd. All rights reserved.

Dynamics of the reaction between the free end of a tethered self-avoiding polymer and a flat penetrable surface: A renormalization group study

The average time tau(r) for one end of a long, self-avoiding polymer to interact for the first time with a flat penetrable surface to which it is attached at the other end is shown here to scale essentially as the square of the chain's contour length N. This result is obtained within the framework of the Wilemski-Fixman approximation to diffusion-limited reactions, in which the reaction time is expressed as a time correlation function of a ``sink'' term. In the present work, this sink-sink correlation function is calculated using perturbation expansions in the excluded volume and the polymer-surface interactions, with renormalization group methods being used to resum the expansion into a power law form. The quadratic dependence of tau(r) on N mirrors the behavior of the average time tau(c) of a free random walk to cyclize, but contrasts with the cyclization time of a free self-avoiding walk (SAW), for which tau(r) similar to N-2.2. A simulation study by Cheng and Makarov J. Phys. Chem. B 114, 3321 (2010)] of the chain-end reaction time of an SAW on a flat impenetrable surface leads to the same N-2.2 behavior, which is surprising given the reduced conformational space a tethered polymer has to explore in order to react. (C) 2014 AIP Publishing LLC.

Combining fractal and deterministic walkers for texture analysis and classification

In this paper,we present a novel texture analysis method based on deterministic partially self-avoiding walks and fractal dimension theory. After finding the attractors of the image (set of pixels) using deterministic partially self-avoiding walks, they are dilated in direction to the whole image by adding pixels according to their relevance. The relevance of each pixel is calculated as the shortest path between the pixel and the pixels that belongs to the attractors. The proposed texture analysis method is demonstrated to outperform popular and state-of-the-art methods (e.g. Fourier descriptors, occurrence matrix, Gabor filter and local binary patterns) as well as deterministic tourist walk method and recent fractal methods using well-known texture image datasets.

Dynamik von Polymerschmelzen und Quellverhalten ungeordneter Netzwerke

Deutsch:Mit Hilfe eines parallelen Molekulardynamik-Programmswurden einfach Modelle von Homopolymerschmelzen simuliert.Langkettige Schmelzen zeigten eine sehr gute Übereinstimmungmit den Vorhersagendes Reptationsmodells. Die intermediären Reptationsbereichemit den vorhergesagtenExponenten konnten wesentlich klarer als bisher verifiziertwerden. Es stellteVerschiedene, gebräuchliche Analyse-Methoden führten jedochzuunterschiedlichen Aussagen für die Verhakungslänge. Fürkurze Kettenbzw. kurze Unterketten wurden in dichten Schmelzendie Abweichungen vom Rouse-Modell aufgezeigt. DieseAbweichungenkönnen als Korrelationslocheffekt interpretiert werden undsteht in teilweiser Übereinstimmung zu den Vorhersagenrenormierter Rouse-Modelle. Aus den Schmelzen wurden Netzwerke in einem speziellenZufallsvernetzungsprozeßhergestellt, der die Bildung von Defektstrukturenunterbindet. Diesewurden bzgl. ihres Quell- und Deformationsverhaltenuntersucht. Der maximaleQuellgrad eines Netzwerkes war bereits bei verhaltnismäßigkurzen Kettenlängenverhakungslimitiert. Die Struktur der Ketten in einem biszum osmotischenGleichgewicht gequollenen Netzwerk unterhalb derMaschengröße ist die überstreckter,selbstvermeidender Ketten mit einer Fraktaldimension von D =1.4,jenseits der Maschengröße (bzw. Verhakungslänge) nehmen siedie Struktur einesIrrfluges an (D = 2). Gequollene Netzwerke zeigten, wie auch in Experimenten, einestarkeZunahme von Dichtefluktuationen, welche unter Verstreckunganisotropwurde und in der Streufunktion zu sogenanntenButterfly-Mustern führt.Diese Fluktuationen sind statischer Natur als Folge desEinfrierenseines ungeordneten Zustandes während der Vernetzung.

A modified gambler's ruin model of polyethylene chains in the amorphous region.

Polyethylene chains in the amorphous region between two crystalline lamellae M unit apart are modeled as random walks with one-step memory on a cubic lattice between two absorbing boundaries. These walks avoid the two preceding steps, though they are not true self-avoiding walks. Systems of difference equations are introduced to calculate the statistics of the restricted random walks. They yield that the fraction of loops is (2M - 2)/(2M + 1), the fraction of ties 3/(2M + 1), the average length of loops 2M - 0.5, the average length of ties 2/3M2 + 2/3M - 4/3, the average length of walks equals 3M - 3, the variance of the loop length 16/15M3 + O(M2), the variance of the tie length 28/45M4 + O(M3), and the variance of the walk length 2M3 + O(M2).

Hierarchical random walks in trace fossils and the origin of optimal search behavior

Efficient searching is crucial for timely location of food and other resources. Recent studies show diverse living animals employ a theoretically optimal scale-free random search for sparse resources known as a Lévy walk, but little is known of the origins and evolution of foraging behaviour and the search strategies of extinct organisms. Here we show using simulations of self-avoiding trace fossil trails that randomly introduced strophotaxis (U-turns) – initiated by obstructions such as ¬¬¬self-trail avoidance or innate cueing – leads to random looping patterns with clustering across increasing scales that is consistent with the presence of Lévy walks. This predicts optimal Lévy searches can emerge from simple behaviours observed in fossil trails. We then analysed fossilized trails of benthic marine organisms using a novel path analysis technique and find the first evidence of Lévy-like search strategies in extinct animals. Our results show that simple search behaviours of extinct animals in heterogeneous environments give rise to hierarchically nested Brownian walk clusters that converge to optimal Lévy patterns. Primary productivity collapse and large-scale food scarcity characterising mass extinctions evident in the fossil record may have triggered adaptation of optimal Lévy-like searches. The findings suggest Lévy-like behaviour has been employed by foragers since at least the Eocene but may have a more ancient origin, which could explain recent widespread observations of such patterns among modern taxa.

Intramolecular conflict : conformation and self-assembly of architecturally complex macromolecules in solution

The solution behavior of linear polymer chains is well understood, having been the subject of intense study throughout the previous century. As plastics have become ubiquitous in everyday life, polymer science has grown into a major field of study. The conformation of a polymer in solution depends on the molecular architecture and its interactions with the surroundings. Developments in synthetic techniques have led to the creation of precision-tailored polymeric materials with varied topologies and functionalities. In order to design materials with the desired properties, it is imperative to understand the relationships between polymer architecture and their conformation and behavior. To meet that need, this thesis investigates the conformation and self-assembly of three architecturally complex macromolecular systems with rich and varied behaviors driven by the resolution of intramolecular conflicts. First we describe the development of a robust and facile synthetic approach to reproducible bottlebrush polymers (Chapter 2). The method was used to produce homologous series of bottlebrush polymers with polynorbornene backbones, which revealed the effect of side-chain and backbone length on the overall conformation in both good and theta solvent conditions (Chapter 3). The side-chain conformation was obtained from a series of SANS experiments and determined to be indistinguishable from the behavior of free linear polymer chains. Using deuterium-labeled bottlebrushes, we were able for the first time to directly observe the backbone conformation of a bottlebrush polymer which showed self-avoiding walk behavior. Secondly, a series of SANS experiments was conducted on a homologous series of Side Group Liquid Crystalline Polymers (SGLCPs) in a perdeuterated small molecule liquid crystal (5CB). Monodomain, aligned, dilute samples of SGLCP-b-PS block copolymers were seen to self-assemble into complex micellar structures with mutually orthogonally oriented anisotropies at different length scales (Chapter 4). Finally, we present the results from the first scattering experiments on a set of fuel-soluble, associating telechelic polymers. We observed the formation of supramolecular aggregates in dilute (≤0.5wt%) solutions of telechelic polymers and determined that the choice of solvent has a significant effect on the strength of association and the size of the supramolecules (Chapter 5). A method was developed for the direct estimation of supramolecular aggregation number from SANS data. The insight into structure-property relationships obtained from this work will enable the more targeted development of these molecular architectures for their respective applications.

A structure-dynamic approach to cortical organization: Number of paths and accessibility

A structure-dynamic approach to cortical systems is reported which is based on the number of paths and the accessibility of each node. The latter measurement is obtained by performing self-avoiding random walks in the respective networks, so as to simulate dynamics, and then calculating the entropies of the transition probabilities for walks starting from each node. Cortical networks of three species, namely cat, macaque and humans, are studied considering structural and dynamical aspects. It is verified that the human cortical network presents the highest accessibility and number of paths (in terms of z-scores). The correlation between the number of paths and accessibility is also investigated as a mean to quantify the level of independence between paths connecting pairs of nodes in cortical networks. By comparing the cortical networks of cat, macaque and humans, it is verified that the human cortical network tends to present the largest number of independent paths of length larger than four. These results suggest that the human cortical network is potentially the most resilient to brain injures. (C) 2009 Elsevier B.V. All rights reserved.