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.

Generalized Metropolis dynamics with a generalized master equation: An approach for time-independent and time-dependent Monte Carlo simulations of generalized spin systems

The extension of Boltzmann-Gibbs thermostatistics, proposed by Tsallis, introduces an additional parameter q to the inverse temperature beta. Here, we show that a previously introduced generalized Metropolis dynamics to evolve spin models is not local and does not obey the detailed energy balance. In this dynamics, locality is only retrieved for q = 1, which corresponds to the standard Metropolis algorithm. Nonlocality implies very time-consuming computer calculations, since the energy of the whole system must be reevaluated when a single spin is flipped. To circumvent this costly calculation, we propose a generalized master equation, which gives rise to a local generalized Metropolis dynamics that obeys the detailed energy balance. To compare the different critical values obtained with other generalized dynamics, we perform Monte Carlo simulations in equilibrium for the Ising model. By using short-time nonequilibrium numerical simulations, we also calculate for this model the critical temperature and the static and dynamical critical exponents as functions of q. Even for q not equal 1, we show that suitable time-evolving power laws can be found for each initial condition. Our numerical experiments corroborate the literature results when we use nonlocal dynamics, showing that short-time parameter determination works also in this case. However, the dynamics governed by the new master equation leads to different results for critical temperatures and also the critical exponents affecting universality classes. We further propose a simple algorithm to optimize modeling the time evolution with a power law, considering in a log-log plot two successive refinements.

Maximum Phonation Time and s/z Ratio in a Large Child Cohort

Aim. The purpose of this study was to provide normal values for maximum phonation time (MPT) and the s/z ratio by examining 1660 children aged 4-12 years and without vocal signs or symptoms. Methods. The technique was based on the sustained emission of the /a/ vowel and fricatives /s/ and /z/. Results. The average of the MPT in children of the different age groups was as follows: 6.09 seconds for the age group 4-6 years (males, 5.97; female, 6.21 seconds), 7.94 seconds for the age group 7-9 years (males, 8.07; females, 7.79 seconds), and 8.98 for the age group 10-12 years (males, 9.05; females, 8.92 seconds). The overall average for males was 7.78 and females 7.64 seconds. The s/z ratio was near 1.0 in most children but above 1.2 in 133 children and below 0.8 in 133 children. Conclusion. These values of MPT and s/z ratio can be used as normative in further pediatric studies.

Time lags of the kilohertz quasi-periodic oscillations in the low-mass X-ray binaries 4U 1608−52 and 4U 1636−53

We studied the energy and frequency dependence of the Fourier time lags and intrinsic coherence of the kilohertz quasi-periodic oscillations (kHz QPOs) in the neutron-star lowmass X-ray binaries 4U 1608−52 and 4U 1636−53, using a large data set obtained with the Rossi X-ray Timing Explorer. We confirmed that, in both sources, the time lags of the lower kHz QPO are soft and their magnitude increases with energy. We also found that: (i) In 4U 1636−53, the soft lags of the lower kHz QPO remain constant at∼30 μs in the QPO frequency range 500–850 Hz, and decrease to ∼10 μs when the QPO frequency increases further. In 4U 1608−52, the soft lags of the lower kHz QPO remain constant at 40 μs up to 800 Hz, the highest frequency reached by this QPO in our data. (ii) In both sources, the time lags of the upper kHz QPO are hard, independent of energy or frequency and inconsistent with the soft lags of the lower kHz QPO. (iii) In both sources the intrinsic coherence of the lower kHz QPO remains constant at ∼0.6 between 5 and 12 keV, and drops to zero above that energy. The intrinsic coherence of the upper kHz QPO is consistent with being zero across the full energy range. (iv) In 4U 1636−53, the intrinsic coherence of the lower kHz QPO increases from ∼0 at ∼600 Hz to ∼1, and it decreases to ∼0.5 at 920 Hz; in 4U 1608−52, the intrinsic coherence is consistent with the same trend. (v) In both sources the intrinsic coherence of the upper kHz QPO is consistent with zero over the full frequency range of the QPO, except in 4U 1636−53 between 700 and 900 Hz where the intrinsic coherence marginally increases. We discuss our results in the context of scenarios in which the soft lags are either due to reflection off the accretion disc or up-/down-scattering in a hot medium close to the neutron star. We finally explore the connection between, on one hand the time lags and the intrinsic coherence of the kHz QPOs, and on the other the QPOs’ amplitude and quality factor in these two sources.