Hidden Markov Random Fields and Direct Search Methods for Medical Image Segmentation

The goal of image segmentation is to simplify the representation of an image to items meaningful and easier to analyze. Medical image segmentation is one of the fundamental problems in image processing field. It aims to provide a crucial decision support to physicians. There is no one way to perform the segmentation. There are several methods based on HMRF. Hidden Markov Random Fields (HMRF) constitute an elegant way to model the problem of segmentation. This modelling leads to the minimization of an energy function. In this paper we investigate direct search methods that are Nelder-Mead and Torczon methods to solve this optimization problem. The quality of segmentation is evaluated on grou…

Approximation of Pore Space with Ellipsoids: A Comparison of a Geometrical Method with a Statistical one

We work with tomographic images of pore space in soil. The images have large dimensions and so in order to speed-up biological simulations (as drainage or diffusion process in soil), we want to describe the pore space with a number of geometrical primitives significantly smaller than the number of voxels in pore space. In this paper, we use the curve skeleton of a volume to segment it into some regions. We describe the method to compute the curve skeleton and to segment it with a simple segment approximation. We approximate each obtained region with an ellipsoid. The set of final ellipsoids represents the geometry of pore space and will be used in future simulations. We compare this method …

Geometric constraint solving: The witness configuration method

Geometric constraint solving is a key issue in CAD, CAM and PLM. The systems of geometric constraints are today studied and decomposed with graph-based methods, before their numerical resolution. However, graph-based methods can detect only the simplest (called structural) dependences between constraints; they cannot detect subtle dependences due to theorems. To overcome these limitations, this paper proposes a new method: the system is studied (with linear algebra tools) at a witness configuration, which is intuitively similar to the unknown one, and easy to compute.

A Robust Multi Stage Technique for Image Binarization of Degraded Historical Documents

International audience; Document image binarization is a central problem in many document analysis systems. Indeed, it represents one of the basic challenges, especially in case of historical documents analysis. In this paper, we propose a novel robust multi stage framework that combines different existing document image thresholding methods for the purpose of getting a better binarization result. CLAHE technique is introduced to significantly enhance contrast in some poor images. The proposed method then uses a hybrid algorithm to partition image into foreground and background. A special procedure is finally applied in order to remove small noise and correct characters morphology. Experime…

INCIDENCE CONSTRAINTS: A COMBINATORIAL APPROACH

The simplest geometric constraints are incidences between points and lines in the projective plane. This problem is universal, in the sense that all algebraic systems reduce to such geometric constraints. Detecting incidence dependences between these geometric constraints is NP-complete. New methods to prove incidence theorems are proposed, which use strictly no computer algebra but only combinatorial arguments.

An Efficient Cooperative Smearing Technique for Degraded Historical Documents Images Segmentation

Segmentation is one of the critical steps in historical document image analysis systems that determines the quality of the search, understanding, recognition and interpretation processes. It allows isolating the objects to be considered and separating the regions of interest (paragraphs, lines, words and characters) from other entities (figures, graphs, tables, etc.). This stage follows the thresholding, which aims to improve the quality of the document and to extract its background from its foreground, also for detecting and correcting the skew that leads to redress the document. Here, a hybrid method is proposed in order to locate words and characters in both handwritten and printed docu…

Special track on Geometric Constraints and Reasoning

Geometric Computing and Reasoning (GCR) aims at emphasizing recent trends in the domain of geometric constraint solving and automated, or computer aided deduction in geometry. This year sees the third edition of this technical track of SAC.

New Geometric Constraint Solving Formulation: Application to the 3D Pentahedron

Geometric Constraint Solving Problems (GCSP) are nowadays routinely investigated in geometric modeling. The 3D Pentahedron problem is a GCSP defined by the lengths of its edges and the planarity of its quadrilateral faces, yielding to an under-constrained system of twelve equations in eighteen unknowns. In this work, we focus on solving the 3D Pentahedron problem in a more robust and efficient way, through a new formulation that reduces the underlying algebraic formulation to a well-constrained system of three equations in three unknowns, and avoids at the same time the use of placement rules that resolve the under-constrained original formulation. We show that geometric constraints can be …

Combination of Hidden Markov Random Field and Conjugate Gradient for Brain Image Segmentation

Image segmentation is the process of partitioning the image into significant regions easier to analyze. Nowadays, segmentation has become a necessity in many practical medical imaging methods as locating tumors and diseases. Hidden Markov Random Field model is one of several techniques used in image segmentation. It provides an elegant way to model the segmentation process. This modeling leads to the minimization of an objective function. Conjugate Gradient algorithm (CG) is one of the best known optimization techniques. This paper proposes the use of the Conjugate Gradient algorithm (CG) for image segmentation, based on the Hidden Markov Random Field. Since derivatives are not available fo…

Session details: Geometric computing and reasoning (GCR)

Optimizing Query Perturbations to Enhance Shape Retrieval

3D Shape retrieval algorithms use shape descriptors to identify shapes in a database that are the most similar to a given key shape, called the query. Many shape descriptors are known but none is perfect. Therefore, the common approach in building 3D Shape retrieval tools is to combine several descriptors with some fusion rule. This article proposes an orthogonal approach. The query is improved with a Genetic Algorithm. The latter makes evolve a population of perturbed copies of the query, called clones. The best clone is the closest to its closest shapes in the database, for a given shape descriptor. Experimental results show that improving the query also improves the precision and complet…

Nonlinear systems solver in floating-point arithmetic using LP reduction

This paper presents a new solver for systems of nonlinear equations. Such systems occur in Geometric Constraint Solving, e.g., when dimensioning parts in CAD-CAM, or when computing the topology of sets defined by nonlinear inequalities. The paper does not consider the problem of decomposing the system and assembling solutions of subsystems. It focuses on the numerical resolution of well-constrained systems. Instead of computing an exponential number of coefficients in the tensorial Bernstein basis, we resort to linear programming for computing range bounds of system equations or domain reductions of system variables. Linear programming is performed on a so called Bernstein polytope: though,…

Hidden Markov random field model and Broyden–Fletcher–Goldfarb–Shanno algorithm for brain image segmentation

International audience; Many routine medical examinations produce images of patients suffering from various pathologies. With the huge number of medical images, the manual analysis and interpretation became a tedious task. Thus, automatic image segmentation became essential for diagnosis assistance. Segmentation consists in dividing the image into homogeneous and significant regions. We focus on hidden Markov random fields referred to as HMRF to model the problem of segmentation. This modelisation leads to a classical function minimisation problem. Broyden-Fletcher-Goldfarb-Shanno algorithm referred to as BFGS is one of the most powerful methods to solve unconstrained optimisation problem. …

Data structures and algorithms for topological analysis

International audience; One of the steps of geometric modeling is to know the topology and/or the geometry of the objects considered. This paper presents different data structures and algorithms used in this study. We are particularly interested by algebraic structures, eg homotopy and homology groups, the Betti numbers, the Euler characteristic, or the Morse-Smale complex. We have to be able to compute these data structures, and for (homotopy and homology) groups, we also want to compute their generators. We are also interested in algorithms CIA and HIA presented in the thesis of Nicolas DELANOUE, which respectively compute the connected components and the homotopy type of a set defined by…

Session details: Geometric computing and reasoning

Robustness and Randomness

The study of robustness problems for computational geometry algorithms is a topic that has been subject to intensive research efforts from both computer science and mathematics communities. Robustness problems are caused by the lack of precision in computations involving floating-point instead of real numbers. This paper reviews methods dealing with robustness and inaccuracy problems. It discusses approaches based on exact arithmetic, interval arithmetic and probabilistic methods. The paper investigates the possibility to use randomness at certain levels of reasoning to make geometric constructions more robust.

An Improved Skew Angle Detection and Correction Technique for Historical Scanned Documents Using Morphological Skeleton and Progressive Probabilistic Hough Transform

International audience; Skew detection is a crucial step for document analysis systems. Indeed, it represents one of the basic challenges, especially in case of historical documents analysis. In this paper, we propose a novel robust skew angle detection and correction technique. Morphological Skeleton is introduced to significantly reduce the amount of data to treat by removing the redundant pixels and keeping only the central curves of the image components. The proposed method then uses Progressive Probabilistic Hough Transform (PPHT) to identify image lines. A special procedure is finally applied in order to estimate the global skew angle of the document image from these detected lines. E…

Hidden Markov Random Field model and BFGS algorithm for Brain Image Segmentation

Brain MR images segmentation has attracted a particular focus in medical imaging. The automatic image analysis and interpretation became a necessity. Segmentation is one of the key operations to provide a crucial decision support to physicians. Its goal is to simplify the representation of an image into items meaningful and easier to analyze. Hidden Markov Random Fields (HMRF) provide an elegant way to model the segmentation problem. This model leads to the minimization problem of a function. BFGS (Broyden-Fletcher-Goldfarb-Shanno algorithm) is one of the most powerful methods to solve unconstrained optimization problem. This paper presents how we combine HMRF and BFGS to achieve a good seg…

Special issue on geometric constraints and reasoning

Witness computation for solving geometric constraint systems

International audience; In geometric constraint solving, the constraints are represented with an equation system F(U, X) = 0, where X denotes the unknowns and U denotes a set of parameters. The target solution for X is noted XT. A witness is a couple (U_W, X_W) such that F(U_W, X_W) = 0. The witness is not the target solution, but they share the same combinatorial features, even when the witness and the target lie on two distinct connected components of the solution set of F(U, X) = 0. Thus a witness enables the qualitative study of the system: the detection of over- and under-constrained systems, the decomposition into irreducible subsystems, the computation of subsystems boundaries. This …

Conjugate Gradient Method for Brain Magnetic Resonance Images Segmentation

Part 8: Pattern Recognition and Image Processing; International audience; Image segmentation is the process of partitioning the image into regions of interest in order to provide a meaningful representation of information. Nowadays, segmentation has become a necessity in many practical medical imaging methods as locating tumors and diseases. Hidden Markov Random Field model is one of several techniques used in image segmentation. It provides an elegant way to model the segmentation process. This modeling leads to the minimization of an objective function. Conjugate Gradient algorithm (CG) is one of the best known optimization techniques. This paper proposes the use of the nonlinear Conjugat…

Editorial message

Geometric Computing and Reasoning (GCR) is a new track of SAC and it is dedicated to the recent trends in the domain of geometric constraint solving and automated, or computer aided, deduction in geometry.

Extending CSG with projections: Towards formally certified geometric modeling

We extend traditional Constructive Solid Geometry (CSG) trees to support the projection operator. Existing algorithms in the literature prove various topological properties of CSG sets. Our extension readily allows these algorithms to work on a greater variety of sets, in particular parametric sets, which are extensively used in CAD/CAM systems. Constructive Solid Geometry allows for algebraic representation which makes it easy for certification tools to apply. A geometric primitive may be defined in terms of a characteristic function, which can be seen as the zero-set of a corresponding system along with inequality constraints. To handle projections, we exploit the Disjunctive Normal Form,…

OPTIMIZATIONS FOR TENSORIAL BERNSTEIN–BASED SOLVERS BY USING POLYHEDRAL BOUNDS

The tensorial Bernstein basis for multivariate polynomials in n variables has a number 3n of functions for degree 2. Consequently, computing the representation of a multivariate polynomial in the tensorial Bernstein basis is an exponential time algorithm, which makes tensorial Bernstein-based solvers impractical for systems with more than n = 6 or 7 variables. This article describes a polytope (Bernstein polytope) with a number of faces, which allows to bound a sparse, multivariate polynomial expressed in the canonical basis by solving several linear programming problems. We compare the performance of a subdivision solver using domain reductions by linear programming with a solver using a c…

Session details: Geometric constraints and reasoning

Using skeleton and Hough transform variant to correct skew in historical documents

International audience; As a main part of several document analysis systems, Skew estimation represents one of the major research challenges, particularly in case of historical documents exploration. In this paper, we propose an original skew angle detection and correction technique. Morphological Skeleton is introduced to considerably diminish the amount of data by eliminating the redundant pixels and preserving only the central curves of the image components. Next, the proposed method uses Progressive Probabilistic Hough Transform (PPHT) to find image lines. At the end, a specific procedure is applied in order to measure the global skew angle of the document image from these identified li…

Approximation of pore space with ellipsoids: a comparison of a geometrical method with a statistical one.

International audience; We work with tomographic images of pore space in soil. The images have large dimensions and so in order to speed-up biological simulations (as drainage or diffusion process in soil), we want to describe the pore space with a number of geometrical primitives significantly smaller than the number of voxels in pore space. In this paper, we use the curve skeleton of a volume to segment it into some regions. We describe the method to compute the curve skeleton and to segment it with a simple segment approximation. We approximate each obtained region with an ellipsoid. The set of final ellipsoids represents the geometry of pore space and will be used in future simulations.…

Numerical decomposition of geometric constraints

Geometric constraint solving is a key issue in CAD/CAM. Since Owen's seminal paper, solvers typically use graph based decomposition methods. However, these methods become difficult to implement in 3D and are misled by geometric theorems. We extend the Numerical Probabilistic Method (NPM), well known in rigidity theory, to more general kinds of constraints and show that NPM can also decompose a system into rigid subsystems. Classical NPM studies the structure of the Jacobian at a random (or generic) configuration. The variant we are proposing does not consider a random configuration, but a configuration similar to the unknown one. Similar means the configuration fulfills the same set of inci…

INTERVAL-BASED TRACING OF STRANGE ATTRACTORS

The method described here relies on interval arithmetic and graph theory to compute guaranteed coverings of strange attractors like Hénon attractor. It copes with infinite intervals, using either a geometric method or a new directed projective interval arithmetic.

Solving the pentahedron problem

Nowadays, all geometric modelers provide some tools for specifying geometric constraints. The 3D pentahedron problem is an example of a 3D Geometric Constraint Solving Problem (GCSP), composed of six vertices, nine edges, five faces (two triangles and three quadrilaterals), and defined by the lengths of its edges and the planarity of its quadrilateral faces. This problem seems to be the simplest non-trivial problem, as the methods used to solve the Stewart platform or octahedron problem fail to solve it. The naive algebraic formulation of the pentahedron yields an under-constrained system of twelve equations in eighteen unknowns. Even if the use of placement rules transforms the pentahedron…

Degraded Historical Documents Images Binarization Using a Combination of Enhanced Techniques

Document image binarization is the initial step and a crucial in many document analysis and recognition scheme. In fact, it is still a relevant research subject and a fundamental challenge due to its importance and influence. This paper provides an original multi-phases system that hybridizes various efficient image thresholding methods in order to get the best binarization output. First, to improve contrast in particularly defective images, the application of CLAHE algorithm is suggested and justified. We then use a cooperative technique to segment image into two separated classes. At the end, a special transformation is applied for the purpose of removing scattered noise and of correcting…

Detecting All Dependences in Systems of Geometric Constraints Using the Witness Method

In geometric constraints solving, the detection of dependences and the decomposition of the system into smaller subsystems are two important steps that characterize any solving process, but nowadays solvers, which are graph-based in most of the cases, fail to detect dependences due to geometric theorems and to decompose such systems. In this paper, we discuss why detecting all dependences between constraints is a hard problem and propose to use the witness method published recently to detect both structural and non structural dependences.We study various examples of constraints systems and show the promising results of the witness method in subtle dependences detection and systems decomposi…

hidden markov random fields and cuckoo search method for medical image segmentation

Segmentation of medical images is an essential part in the process of diagnostics. Physicians require an automatic, robust and valid results. Hidden Markov Random Fields (HMRF) provide powerful model. This latter models the segmentation problem as the minimization of an energy function. Cuckoo search (CS) algorithm is one of the recent nature-inspired meta-heuristic algorithms. It has shown its efficiency in many engineering optimization problems. In this paper, we use three cuckoo search algorithm to achieve medical image segmentation.

Vers un modeleur géométrique déclaratif

International audience; no abstract

Using the witness method to detect rigid subsystems of geometric constraints in CAD

International audience; This paper deals with the resolution of geometric constraint systems encountered in CAD-CAM. The main results are that the witness method can be used to detect that a constraint system is over-constrained and that the computation of the maximal rigid subsystems of a system leads to a powerful decomposition method. In a first step, we recall the theoretical framework of the witness method in geometric constraint solving and extend this method to generate a witness. We show then that it can be used to incrementally detect over-constrainedness. We give an algorithm to efficiently identify all maximal rigid parts of a geometric constraint system. We introduce the algorit…

Solution isolation strategies for the Bernstein polytopes-based solver

The Bernstein polytopes-based solver is a new method developed to solve systems of nonlinear equations, which often occur in Geometric Constraint Solving Problems. The principle of this solver is to linearize nonlinear monomials and then to solve the resulting linear programming problems, through linear programming. However, without any strategy for the isolation of the many solutions of multiple-solution systems, this solver is slow in practice. To overcome this problem, we propose in this work, a study of several strategies for solution isolation, through the split of solution boxes into several subboxes, according to three main steps answering the questions: when, where, and how to perfo…

Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems

International audience; This paper describes new ways to tackle several important problems encountered in geometric constraint solving, in the context of CAD, and which are linked to the handling of under- and over-constrained systems. It presents a powerful decomposition algorithm of such systems. Our methods are based on the witness principle whose theoretical background is recalled in a first step. A method to generate a witness is then explained. We show that having a witness can be used to incrementally detect over-constrainedness and thus to compute a well-constrained boundary system. An algorithm is introduced to check if anchoring a given subset of the coordinates brings the number …

Interrogating witnesses for geometric constraint solving

International audience; Classically, geometric constraint solvers use graph-based methods to decompose systems of geometric constraints. These methods have intrinsic limitations, which the witness method overcomes; a witness is a solution of a variant of the system. This paper details the computation of a basis of the vector space of free infinitesimal motions of a typical witness, and explains how to use this basis to interrogate the witness for dependence detection. The paper shows that the witness method detects all kinds of dependences: structural dependences already detectable by graph-based methods, but also non-structural dependences, due to known or unknown geometric theorems, which…