Segmentation of convex cells with partially undefined edges

This paper presents an algorithm for segmentation of convex cells with partially undefined edges based on application of a marker-controlled watershed transform to a combination of a source grayscale image and the result of a “geodesic distance” morphological operation, applied to the result of binarization of a source image. The presented approach is used in computer image processing systems for analysis of several industrial materials. The text was submitted by the authors in English. Ilia V. Safonov received his MS degree in automatic and electronic engineering from Moscow Engineering Physics Institute/University (MEPhI), Russia in 1994 and his PhD degree in computer science from MEPhI in 1997. Since 1998 he is an associate professor of faculty of Cybernetics of MEPhI while conducting researches in image segmentation, features extraction and pattern recognition problems. Since 2004, Dr. I. Safonov has joint Image Enhancement Technology Group, Printing Technology Lab, Samsung Research Center, Moscow, Russia where he is engaged in photo, video, and document image enhancement projects. Konstantin A. Kryzhanovsky received the MS degree in cybernetics from Moscow Engineering Physics Institute/University (MEPhI), Russia in 2000. Since 2006 he is an assistant professor of faculty of Cybernetics of MEPhI. He is presently working towards his Ph.D. degree. His current research interests include image processing and pattern recognition. Gennady N. Mavrin received his MS degree in automatic and electronic engineering from Moscow Engineering Physics Institute/University (MEPhI), Russia in 1998. Since 2002 he is an assistant professor of faculty of Cybernetics of MEPhI. He is currently pursuing the PhD degree. His research interests include image segmentation and feature extraction problems.     

Segmentation of two-dimensional boundaries using the chain code

We divide the boundary of a two-dimensional object into segments, each of which is either straight or a circular arc; associated with the segment end-points are angle measures that can be used to match an object with a transformed (rotated, scaled) version of itself. The chain code, easily extracted from the boundary pixels, is the basis of this division. The approach avoids problems common to many of the existing methods for identification of curvature extrema: sensitivity to noise and dependence on parameters that are chosen empirically.

To each section of the boundary we assign a code that represents the change in slope between it and the previous section. This set of codes is integrated and thus provides a measure of the total directional change relative to the first section. For a closed object, the sequence of these sums is periodic, and one cycle can be plotted as a function of arc length, s. Such a plot can be shown to contain only straight lines: those that are not parallel to the s-axis (representing circular arcs on the original boundary of the object) and those that are (representing straight sections on the boundary).

This paper describes a recursive procedure for dividing the digital version of the curve described above into its linear segments. Each segment represents an arc that is the best fit to a portion of the original boundary; the angle which is defined by the arc is identical to the angle change of the edge in the same section, and the length of the arc is identical to that of the edge. The recursive procedure measures the error (for each value of arc length) between a proposed fitting line and the actual value of cumulative angle; where the error is maximum, and above a threshold, the line is segmented. The procedure is repeated until the error is sufficiently small. The breakpoints thus indicate the location and value of points of greatest curvature change.

A formal definition of the procedure is given, and it is shown to perform well for rotated, scaled and noisy objects.     

多分类支持向量机分割彩色癌细胞图像

在细胞彩色图像处理中,为了有效地计算与分析细胞各特征值,对细胞图像的精确的三域分割是细胞自动分析与识别的一个关键环节。提出利用多分类支持向量机对细胞彩色图像进行背景、胞浆与核的一次性三域分割,并且通过聚类分析的方法实现了在线训练,实验表明,该方法在细胞彩色图像的多域分割上,能获得较高的分割精度和较好的鲁棒性。     

Segmentation of microscope images of living cells

This paper describes a segmentation method combining a texture based technique with a contour based method. The technique is designed to enable the study of cell behaviour over time by segmenting brightfield microscope image sequences. The technique was tested on artificial images, based on images of living cells and on real sequences acquired from microscope observations of neutrophils and lymphocytes as well as on a sequence of MRI images. The results of the segmentation are compared with the results of the watershed and snake segmentation methods. The results show that the method is both effective and practical.

Run-time detection of undefined variables considered essential

Access to an undefined variable—one which has never been assigned a value—can be detected by automatic means. However, today's compilers do not detect undefined variables comprehensively, and the environment dependence of these errors often allows them to evade normal testing procedures. Language standards for Pascal, Modula-2 and Ada specify the circumstances in which the undefined variable access should cause an error trap. The logic of undefined in these standards is compared, revealing problems in security, implementation effort and consistency with accepted programming practice. An alternative logic, ‘undefined if totally-undefined’ is proposed.     

Manifold-based surfaces with boundaries

We present a manifold-based surface construction extending the C^∞ construction of Ying and Zorin (2004). Our surfaces allow for piecewise-smooth boundaries and have an improved derivative and visual behavior. Their degree of smoothness can be controlled by the user. Two-flexibility of our surface construction is confirmed numerically for a range of local mesh configurations.     

融合边界信息的高分辨率遥感影像分割优化算法

目的 针对目前区域分割算法获取的区域边界与真实地物边界不一致问题,利用高分辨率遥感影像地物内具有均质性和地物间边缘信息突出的特点,提出一种融合边界信息的高分辨率遥感影像分割优化算法。方法 首先采用Canny算法对遥感影像进行边缘提取并进行边缘连接处理,产生闭合边界;然后将边界与初始分割结果进行融合处理,获得新的分割结果;最后在闭合边界约束下,基于灰度相似性准则对新的分割结果进行区域合并,获得优化后的最终分割结果。结果 采用本文提出的分割优化算法对Mean Shift算法和eCognition软件获得的分割结果进行优化处理,优化后的分割结果与初始分割结果相比正确分割率（RR）平均提高了4%,验证了本文算法的有效性。结论 该优化算法适用性广,可优化基于区域、基于边界和基于聚类等多种分割方法,同时该算法既能保持高分辨率遥感影像分割的区域完整性,又能保持地物边缘细节特征,提高了分割精度。     

Meshing volumes with curved boundaries

This paper introduces a three-dimensional mesh generation algorithm for domains whose boundaries are curved surfaces, possibly with sharp features. The algorithm combines a Delaunay-based surface mesher with a Ruppert-like volume mesher, resulting in a greedy scheme to sample the interior and the boundary of the domain simultaneously. The algorithm constructs provably good meshes, it gives control on the size of the mesh elements through a user-defined sizing field, and it guarantees the accuracy of the approximation of the domain boundary. A notable feature is that the domain boundary has to be known only through an oracle that can tell whether a given point lies inside the object and whether a given line segment intersects the boundary. This makes the algorithm generic enough to be applied to domains with a wide variety of boundary types, such as implicit surfaces, polyhedra, level-sets in 3D gray-scaled images, or point-set surfaces.     

On encoding boundaries with quadtrees

The ``line quadtree' data structure hierarchically represents a region and its boundary. Based on the standard quadtree, each node in this structure stores adjacency information as well. While line quadtrees use the same amount of space as standard qaudtrees, they facilitate several region processing algorithms. In particular, we describe efficient algorithms for boundary and superimposing two maps encoded as line quadtrees.     

One-dimensional quantum walks with absorbing boundaries

In this paper we analyze the behavior of quantum random walks. In particular, we present several new results for the absorption probabilities in systems with both one and two absorbing walls for the one-dimensional case. We compute these probabilities both by employing generating functions and by use of an eigenfunction approach. The generating function method is used to determine some simple properties of the walks we consider, but appears to have limitations. The eigenfunction approach works by relating the problem of absorption to a unitary problem that has identical dynamics inside a certain domain, and can be used to compute several additional interesting properties, such as the time dependence of absorption. The eigenfunction method has the distinct advantage that it can be extended to arbitrary dimensionality. We outline the solution of the absorption probability problem of a (D−1)-dimensional wall in a D-dimensional space.     

ImageNet Auto-Annotation with Segmentation Propagation

ImageNet is a large-scale hierarchical database of object classes with millions of images.We propose to automatically populate it with pixelwise object-background segmentations, by leveraging existing manual annotations in the form of class labels and bounding-boxes. The key idea is to recursively exploit images segmented so far to guide the segmentation of new images. At each stage this propagation process expands into the images which are easiest to segment at that point in time, e.g. by moving to the semantically most related classes to those segmented so far. The propagation of segmentation occurs both (a) at the image level, by transferring existing segmentations to estimate the probability of a pixel to be foreground, and (b) at the class level, by jointly segmenting images of the same class and by importing the appearance models of classes that are already segmented. Through experiments on 577 classes and 500k images we show that our technique (i) annotates a wide range of classes with accurate segmentations; (ii) effectively exploits the hierarchical structure of ImageNet; (iii) scales efficiently, especially when implemented on superpixels; (iv) outperforms a baseline GrabCut (Rother et al. 2004) initialized on the image center, as well as segmentation transfer from a fixed source pool and run independently on each target image (Kuettel and Ferrari 2012). Moreover, our method also delivers state-of-the-art results on the recent iCoseg dataset for co-segmentation.     

基于TBL的手写字体分段技术

TBL是一种被广泛应用于自然语言处理的基于转换的机器学习算法,将这种算法扩展到OCR领域,用来进行字符分割的计算.字符分割是字符识别的一个步骤,它的准确度在一定程度上关系到最终识别结果.为了比较试验的结果,收集了很多的手写字体,通过规则的提取和应用,在探测分段边界过程中也能达到令人满意的结果.     

虚拟现实的图形生成技术

虚拟现实是一种高度逼真的模拟人在自然环境中视、听、动等行为的人机界面。图形生成是虚拟现实技术的重要瓶颈。本文对面向虚拟现实的实时图形生成技术及其发展情况作了详细的介绍和综述。其主要内容是图形生成的硬件体系结构以及在虚拟现实的真实感图形生成中用于加速的各种有效技术。     

引入差分图像具有多重特性的图像分割模型

大多数经典活动轮廓模型只具有某些方面的优势,不能同时满足处理复杂图像的要求,对此提出一种具有多重分割特性的分割模型.模型通过引入差分图像,将差分图像的BGFRLS模型作为全局控制项,以保证模型能够最大限度地检测到所有的目标边缘;其次,将长度项设为局部项,使得分割进一步精确化,并将Li方法中的惩罚项加入到模型中,避免了重新初始化水平集函数,提高了分割效率;最后,模型在全局控制项和局部控制项之间引入了自适应权值,避免了过多的参数设置.通过上述方法使得模型具有如下优点:1)具有更强的全局分割性;2)可以分割灰度不均匀的图像,而且能够有效地检测出虚弱目标边缘;3)算法具有一定鲁棒性,能够克服一定噪声.实验表明,该模型在保证分割效率的前提下可以分割灰度不均匀的图像,而且能够有效检测出虚弱目标边缘,此外还具有更强的全局分割性,并能抵御一定噪声.     

Stabbing parallel segments with a convex polygon

We present an algorithm that, given a set of n parallel line segments in the plane, finds a convex polygon whose boundary intersects each segment at least once or that determines that none exists. Our algorithm runs in O(nlogn) steps and linear space, which is optimal. Our solution involves a reduction to a bipartite stabbing problem, using a “point-sweeping” or “chain-unwrapping” technique. We use geometric duality to solve bipartite stabbing. We also indicate how to extend our algorithm to find the convex polygon with minimum area or perimeter that intersects each segment.     

Learning linear PCA with convex semi-definite programming

The aim of this paper is to learn a linear principal component using the nature of support vector machines (SVMs). To this end, a complete SVM-like framework of linear PCA (SVPCA) for deciding the projection direction is constructed, where new expected risk and margin are introduced. Within this framework, a new semi-definite programming problem for maximizing the margin is formulated and a new definition of support vectors is established. As a weighted case of regular PCA, our SVPCA coincides with the regular PCA if all the samples play the same part in data compression. Theoretical explanation indicates that SVPCA is based on a margin-based generalization bound and thus good prediction ability is ensured. Furthermore, the robust form of SVPCA with a interpretable parameter is achieved using the soft idea in SVMs. The great advantage lies in the fact that SVPCA is a learning algorithm without local minima because of the convexity of the semi-definite optimization problems. To validate the performance of SVPCA, several experiments are conducted and numerical results have demonstrated that their generalization ability is better than that of regular PCA. Finally, some existing problems are also discussed.