A novel MAP-MRF approach for multispectral image contextual classification using combination of suboptimal iterative algorithms

In this paper we present a novel approach for multispectral image contextual classification by combining iterative combinatorial optimization algorithms. The pixel-wise decision rule is defined using a Bayesian approach to combine two MRF models: a Gaussian Markov Random Field (GMRF) for the observations (likelihood) and a Potts model for the a priori knowledge, to regularize the solution in the presence of noisy data. Hence, the classification problem is stated according to a Maximum a Posteriori (MAP) framework. In order to approximate the MAP solution we apply several combinatorial optimization methods using multiple simultaneous initializations, making the solution less sensitive to the initial conditions and reducing both computational cost and time in comparison to Simulated Annealing, often unfeasible in many real image processing applications. Markov Random Field model parameters are estimated by Maximum Pseudo-Likelihood (MPL) approach, avoiding manual adjustments in the choice of the regularization parameters. Asymptotic evaluations assess the accuracy of the proposed parameter estimation procedure. To test and evaluate the proposed classification method, we adopt metrics for quantitative performance assessment (Cohen`s Kappa coefficient), allowing a robust and accurate statistical analysis. The obtained results clearly show that combining sub-optimal contextual algorithms significantly improves the classification performance, indicating the effectiveness of the proposed methodology. (C) 2010 Elsevier B.V. All rights reserved.

PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Heteroscedastic controlled calibration model applied to analytical chemistry

In chemical analyses performed by laboratories, one faces the problem of determining the concentration of a chemical element in a sample. In practice, one deals with the problem using the so-called linear calibration model, which considers that the errors associated with the independent variables are negligible compared with the former variable. In this work, a new linear calibration model is proposed assuming that the independent variables are subject to heteroscedastic measurement errors. A simulation study is carried out in order to verify some properties of the estimators derived for the new model and it is also considered the usual calibration model to compare it with the new approach. Three applications are considered to verify the performance of the new approach. Copyright (C) 2010 John Wiley & Sons, Ltd.

FROM TRISECTIONS IN MODULE CATEGORIES TO QUASI-DIRECTED COMPONENTS

In this paper, we define and study a special type of trisections in a module category, namely the compact trisections which characterize quasi-directed components. We apply this notion to the study of laura algebras and we use it to define a class of algebras with predictable Auslander-Reiten components.

Approaches for multicopper oxidases in the design of electrochemical sensors for analytical applications

We report an effective approach for the construction of a biomimetic sensor of multicopper oxidases by immobilizing a cyclic-tetrameric copper(II) species, containing the ligand (4-imidazolyl)ethylene-2-amino-1-ethylpyridine (apyhist), in the Nafion (R) membrane on a vitreous carbon electrode surface. This complex provides a tetranuclear arrangement of copper ions that allows an effective reduction of oxygen to water, in a catalytic cycle involving four electrons. The electrochemical reduction of oxygen was studied at pH 9.0 buffer solution by using cyclic voltammetry, chronoamperometry, rotating disk electrode voltammetry and scanning electrochemical microscopy techniques. The mediator shows good electrocatalytic ability for the reduction of O(2) at pH 9.0, with reduction of overpotential (350 mV) and increased current response in comparison with results obtained with a bare glassy carbon electrode. The heterogeneous rate constant (k(ME)`) for the reduction of O(2) at the modified electrode was determined by using a Koutecky-Levich plot. In addition, the charge transport rate through the coating and the apparent diffusion coefficient of O(2) into the modifier film were also evaluated. The overall process was found to be governed by the charge transport through the coating, occurring at the interface or at a finite layer at the electrode/coating interface. The proposed study opens up the way for the development of bioelectronic devices based on molecular recognition and self-organization. (C) 2010 Elsevier Ltd. All rights reserved.

Exploring Liquid Sequential Injection Chromatography To Teach Fundamentals of Separation Methods: A Very Fast Analytical Chemistry Experiment

Fundacao de Amparo a Pesquisa do Estado de Sao Paulo (FAPESP)

Development of an Analytical Methodology for Quantification of Strong Acid in Diesel Oil

Many factors can affect the quality of diesel oil, in particular the degradation processes that are directly related to some organosulfur compounds. During the degradation process, these compounds are oxidized into their corresponding sulfonic acids, generating a strong acid content during the process. p-Toluene sulfonic acid analysis was performed using the linear sweep voltammetry technique with a platinum ultramicroelectrode in aqueous solution containing 3 mol L(-1) potassium chloride. An extraction step was introduced prior to the voltammetric detection in order to avoid the adsorption of organic molecules, which inhibit the electrochemical response. The extraction step promoted the transference of sulfonic acid from the diesel oil to an aqueous phase. The method was accurate and reproducible, with detection and quantification limits of 5 ppm and 15 ppm, respectively. Recovery of sulfonic acid was around 90%.

Graphite-silicone rubber composite electrode: Preparation and possibilities of analytical application

Composite electrodes were prepared using graphite powder and silicone rubber in different compositions. The use of such hydrophopic materials interned to diminish the swallowing observed in other cases when the electrodes are used in aqueous solutions for a long time. The composite was characterized for the response reproducibility, ohmic resistance, thermal behavior and active area. The voltammetric response in relation to analytes with known voltammetric behavior was also evaluated, always in comparison with the glassy carbon. The 70% (graphite, w/w) composite electrode was used in the quantitative determination of hydroquinone (HQ) in a DPV procedure in which a detection limit of 5.1 x 10(-8) mol L-1 was observed. HQ was determined in a photographic developer sample with errors lower then 1% in relation to the label value. (c) 2007 Elsevier B.V. All rights reserved.

Analytical Potentialities of Carbon Nanotube/Silicone Rubber Composite Electrodes: Determination of Propranolol

A new composite electrode based on multiwall carbon nanotubes (MWCNT) and silicone-rubber (SR) was developed and applied to the determination of propranolol in pharmaceutical formulations. The effect of using MWCNT/graphite mixtures in different proportions was also investigated. Cyclic voltammetry and electrochemical impedance spectroscopy were used for electrochemical characterization of different electrode compositions. Propranolol was determined using MWCNT/SR 70% (m/m) electrodes with linear dynamic ranges up to 7.0 mu molL(-1) by differential pulse and up to 5.4 mu molL(-1) by square wave voltammetry, with LODs of 0.12 and 0.078 mu molL(-1), respectively. Analysis of commercial samples agreed with that obtained by the official spectrophotometric method. The electrode is mechanically robust and presented reproducible results and a long useful life.

Diagnostics for the Developing World: Microfluidic Paper-Based Analytical Devices

Microfluidic paper-based analytical devices (mu PADs) are a new class of point-of-care diagnostic devices that are inexpensive, easy to use, and designed specifically for use in developing countries. (To listen to a podcast about this feature, please go to the Analytical Chemistry multimedia page at pubs.acs.org/page/ancham/audio/index.html.)

On the molecular mass of the extracellular hemoglobin of Glossoscolex paulistus: Analytical ultracentrifugation reexamination

The giant extracellular hemoglobin of Glossoscolex paulistus (HbGp) is constituted by Subunits containing heme groups with molecular masses (M) in the range of 15 to 19 kDa, monomers of 16 kDa (d), and trimers of 51 to 52 kDa (abc) linked by nonheme structures named linkers of 24 to 32 kDa (L). HbGp is homologous to Lumbricus terrestris hemoglobin (HbLt). Several reports propose M of HbLt in the range of 3.6 to 4.4 MDa. Based on subunits M determined by mass spectrometry and assuming HbGp stoichiometry of 12(abcd)(3)L(3) (Vinogradov model) plus 144 heme groups, a Value of M for HbGp oligomer of 3560 kDa can be predicted. This Value is nearly 500 kDa higher than the unique HbGp M Value reported in the literature. In the current work, sedimentation velocity analytical ultracentrifugation (AUC) experiments were performed to obtain M for HbGp in oxy and cyano-met forms. s(20,w)(0), values of 58.1 +/- 0.2 S and 59.6 +/- 0.2 S, respectively, for the two oxidation forms were obtained. The ratio between sedimentation and diffusion coefficients supplied values for M of approximately 3600 100 and 3700 100 kDa for oxy and cyano-met HbGp forms, respectively. An independent determination of the partial specific volume, V(bar), for HbGp was performed based on density measurements, providing a value of 0.764 +/- 0.008, in excellent agreement with the estimates from SEDFIT software. Our results show total consistency between M obtained by AUC and recent partial characterization by mass spectrometry. Therefore, HbGp possesses M very close to that of HbLt, suggesting an oligomeric assembly in agreement with the Vinogradov model. (c) 2008 Elsevier Inc. All rights reserved.

Analytical Assessment of a Home Made Capillary Electrophoresis Equipment with Linear Charge Coupled Device for Visible Light Absorption Detection in the Determination of Food Dyes

The performance of modular home made capillary electrophoresis equipment with spectrophotometric detection, at a visible region by means of a miniaturized linear charge coupled device, was evaluated for the determination of four food dyes. This system presents a simple but efficient home made cell detection scheme. A computer program that converts the spectral data after each run into the electropherograms was developed to evaluate the analytical parameters. The dyes selected for analytical evaluation of the system were Brilliant Blue FCF, Fast Green FCF, Sunset Yellow FCF, and Amaranth. Separation was carried out in a 29cm length and 75 mu m I.D fused silica capillary, using 10mmolL-1 borate buffer at pH 9, with separation voltage of 7.5kV. The detection limits for the dyes were between 0.3 and 1.5mgL-1 and the method presented adequate linearity over the ranges studied, with correlation coefficients greater than 0.99. The method was applied for determination and quantification of these dyes in fruit juices and candies.