Fuzzy Connectedness Image Segmentation in Graph Cut Formulation: A Linear-Time Algorithm and a Comparative Analysis

A deep theoretical analysis of the graph cut image segmentation framework presented in this paper simultaneously translates into important contributions in several directions. The most important practical contribution of this work is a full theoretical description, and implementation, of a novel powerful segmentation algorithm, GC(max). The output of GC(max) coincides with a version of a segmentation algorithm known as Iterative Relative Fuzzy Connectedness, IRFC. However, GC(max) is considerably faster than the classic IRFC algorithm, which we prove theoretically and show experimentally. Specifically, we prove that, in the worst case scenario, the GC(max) algorithm runs in linear time with respect to the variable M=|C|+|Z|, where |C| is the image scene size and |Z| is the size of the allowable range, Z, of the associated weight/affinity function. For most implementations, Z is identical to the set of allowable image intensity values, and its size can be treated as small with respect to |C|, meaning that O(M)=O(|C|). In such a situation, GC(max) runs in linear time with respect to the image size |C|. We show that the output of GC(max) constitutes a solution of a graph cut energy minimization problem, in which the energy is defined as the a"" (a) norm ayenF (P) ayen(a) of the map F (P) that associates, with every element e from the boundary of an object P, its weight w(e). This formulation brings IRFC algorithms to the realm of the graph cut energy minimizers, with energy functions ayenF (P) ayen (q) for qa[1,a]. Of these, the best known minimization problem is for the energy ayenF (P) ayen(1), which is solved by the classic min-cut/max-flow algorithm, referred to often as the Graph Cut algorithm. We notice that a minimization problem for ayenF (P) ayen (q) , qa[1,a), is identical to that for ayenF (P) ayen(1), when the original weight function w is replaced by w (q) . Thus, any algorithm GC(sum) solving the ayenF (P) ayen(1) minimization problem, solves also one for ayenF (P) ayen (q) with qa[1,a), so just two algorithms, GC(sum) and GC(max), are enough to solve all ayenF (P) ayen (q) -minimization problems. We also show that, for any fixed weight assignment, the solutions of the ayenF (P) ayen (q) -minimization problems converge to a solution of the ayenF (P) ayen(a)-minimization problem (ayenF (P) ayen(a)=lim (q -> a)ayenF (P) ayen (q) is not enough to deduce that). An experimental comparison of the performance of GC(max) and GC(sum) algorithms is included. This concentrates on comparing the actual (as opposed to provable worst scenario) algorithms' running time, as well as the influence of the choice of the seeds on the output.

Decay of energy and suppression of Fermi acceleration in a dissipative driven stadium-like billiard

The behavior of the average energy for an ensemble of non-interacting particles is studied using scaling arguments in a dissipative time-dependent stadium-like billiard. The dynamics of the system is described by a four dimensional nonlinear mapping. The dissipation is introduced via inelastic collisions between the particles and the moving boundary. For different combinations of initial velocities and damping coefficients, the long time dynamics of the particles leads them to reach different states of final energy and to visit different attractors, which change as the dissipation is varied. The decay of the average energy of the particles, which is observed for a large range of restitution coefficients and different initial velocities, is described using scaling arguments. Since this system exhibits unlimited energy growth in the absence of dissipation, our results for the dissipative case give support to the principle that Fermi acceleration seems not to be a robust phenomenon. (C) 2012 American Institute of Physics. [http://dx.doi.org/10.1063/1.3699465]

ENERGY AND VOLUME OF VECTOR FIELDS ON SPHERICAL DOMAINS

We present a "boundary version" for theorems about minimality of volume and energy functionals on a spherical domain of an odd-dimensional Euclidean sphere.

Fourier´s law from a chain of coupled anharmonic oscillators under energy conserving shot noise.

We analyze the transport of heat along a chain of particles interacting through anharmonic potentials consisting of quartic terms in addition to harmonic quadratic terms and subject to heat reservoirs at its ends. Each particle is also subject to an impulsive shot noise with exponentially distributed waiting times whose effect is to change the sign of its velocity, thus conserving the energy of the chain. We show that the introduction of this energy conserving stochastic noise leads to Fourier's law. That is for large system size L the heat current J behaves as J ‘approximately’ 1/L, which amounts to say that the conductivity k is constant. The conductivity is related to the current by J = kΔT/L, where ΔT is the difference in the temperatures of the reservoirs. The behavior of heat conductivity k for small intensities¸ of the shot noise and large system sizes L are obtained by assuming a scaling behavior of the type k = ‘L POT a Psi’(L’lambda POT a/b’) where a and b are scaling exponents. For the pure harmonic case a = b = 1, characterizing a ballistic conduction of heat when the shot noise is absent. For the anharmonic case we found values for the exponents a and b smaller then 1 and thus consistent with a superdiffusive conduction of heat without the shot noise. We also show that the heat conductivity is not constant but is an increasing function of temperature.

Study of surface free energy on a lattice-gas model applied to Liquid bridge

The pulmonary crackling and the formation of liquid bridges are problems that for centuries have been attracting the attention of scientists. In order to study these phenomena, it was developed a canonical cubic lattice-gas­ like model to explain the rupture of liquid bridges in lung airways [A. Alencar et al., 2006, PRE]. Here, we further develop this model and add entropy analysis to study thermodynamic properties, such as free energy and force. The simulations were performed using the Monte Carlo method with Metropolis algorithm. The exchange between gas and liquid particles were performed randomly according to the Kawasaki dynamics and weighted by the Boltzmann factor. Each particle, which can be solid (s), liquid (l) or gas (g), has 26 neighbors: 6 + 12 + 8, with distances 1, √2 and √3, respectively. The energy of a lattice's site m is calculated by the following expression: Em = ∑k=126 Ji(m)j(k) in witch (i, j) = g, l or s. Specifically, it was studied the surface free energy of the liquid bridge, trapped between two planes, when its height is changed. For that, was considered two methods. First, just the internal energy was calculated. Then was considered the entropy. It was fond no difference in the surface free energy between this two methods. We calculate the liquid bridge force between the two planes using the numerical surface free energy. This force is strong for small height, and decreases as the distance between the two planes, height, is increased. The liquid-gas system was also characterized studying the variation of internal energy and heat capacity with the temperature. For that, was performed simulation with the same proportion of liquid and gas particle, but different lattice size. The scale of the liquid-gas system was also studied, for low temperature, using different values to the interaction Jij.