Two graph theory based methods for identifying the pectoral muscle in mammograms

Two image segmentation methods based on graph theory are used in conjunction with active contours to segment the pectoral muscle in screening mammograms. One method is based on adaptive pyramids (AP) and the other is based on minimum spanning trees (MST). The algorithms are tested on a public data set of mammograms and results are compared with previously reported methods. In 80% of the images, the boundary of the segmented regions has average error less than 2 mm. In 82 of 84 images, the boundary of the pectoral muscle found by the AP algorithm has average error less than 5 mm.     

基于Mumford-Shah理论的最小生成树图像分割方法

基于最小生成树的图像分割方法虽然具有较快的分割速度,然而这类方法的结果较为粗糙、冗杂.结合Mumford-Shah理论,提出了一种优化的方法.通过考虑图像中区域间的结合程度以及各区域的几何性质,计算区域间基于结合度的权值并将之加入到最小生成树图像分割方法的区域合并判断公式中,使相互结合较好的区域更易于合并.该方法能够在保留目标区域间较弱边缘的同时,很好地合并目标区域内部结合较好的区域,并得剑简洁平滑的轮廓.     

基于图论的彩色图像快速分割方法研究

基于图论的图像分割方法作为一种全局的分割方法,当图像的信息量增大时,问题求解将非常耗时.提出一种基于图论的彩色图像快速分割方法,该方法首先用区域生长法将彩色图像划分为内部相似的一些区域,再用最小支撑树MST(Minimum spanning tree)方法在这些区域之间进行分割,产生最终的分割图像.以彩色图像作为研究对象,实验结果表明,相对于传统的MST图论分割方法,该方法在取得较好分割效果的同时,提高了分割速度.     

基于最小生成树的图像分割

基于最小生成树思想,给出了一种利用改进的最小生成树进行图像分割的方案,减少了最小生成树的构建过程,对初分割的结果利用NNG算法进行合并。该方案节约了分割时间,并且对分割后的图像进行了有效的合并,达到了较好的分割效果。     

Salient object detection using color spatial distribution and minimum spanning tree weight

Salient object detection is very useful in many computer vision applications such as image segmentation, content-based image editing and object recognition. In this paper, we present a salient object detection algorithm by using color spatial distribution (CSD) and minimum spanning tree weight (MSTW). We first use a segmentation algorithm to decompose an image into superpixel-level elements, then use these elements as nodes to construct a minimum spanning tree (MST), each connected edge weight is the mean color difference between two nodes. CSD of each element can be computed by integrating color, spatial distance and MSTW. Note that if the color of one element is the most widely distributed over the entire image, it should have the biggest CSD value, we regard this element as a background node (BG Node). Then we use the MSTW between other element and BG node to generate a MSTW map. The superpixel-level saliency map can be obtained by combining the CSD map and MSTW map. Finally, we use a guided filter to get the pixel-level saliency map. Experimental results on two databases demonstrate that our proposed method outperforms other previous state-of-the-art approaches.     

一种基于图的颜色纹理区域分割方法

针对传统基于图论的图像分割方法在分割纹理图像或有突变边缘的图像时,分割效果不理想的问题,提出了一种新的基于图论的颜色一纹理区域分割方法,该方法采用分块的小波能量直方图与三阶颜色矩组成块特征向量生成图顶点的集合,同时根据块间距离进行加权,计算块间的相似度,作为图的边权值,再利用最小生成树的方法进行图像分割,方法有效地弥补了传统基于图论的分割方法中的两个问题.实验结果表明,该算法具有良好的分割准确性与鲁棒性.     

Handwritten Chinese text line segmentation by clustering with distance metric learning

Separating text lines in unconstrained handwritten documents remains a challenge because the handwritten text lines are often un-uniformly skewed and curved, and the space between lines is not obvious. In this paper, we propose a novel text line segmentation algorithm based on minimal spanning tree (MST) clustering with distance metric learning. Given a distance metric, the connected components (CCs) of document image are grouped into a tree structure, from which text lines are extracted by dynamically cutting the edges using a new hypervolume reduction criterion and a straightness measure. By learning the distance metric in supervised learning on a dataset of pairs of CCs, the proposed algorithm is made robust to handle various documents with multi-skewed and curved text lines. In experiments on a database with 803 unconstrained handwritten Chinese document images containing a total of 8,169 lines, the proposed algorithm achieved a correct rate 98.02% of line detection, and compared favorably to other competitive algorithms.     

一种改进的基于图论的图像分割方法

由于传统基于图论的图像分割方法是基于像素级别的,随着像素的增多,其应用也受到了限制,因此,提出一种改进的图像分割方法。该图像分割方法利用Dijkstra算法,将图像的像素点聚集形成超像素;应用Kruskal算法,得到最小生成树,确定并删除最小生成树的不一致边,完成图像分割。实验结果表明,改进方法分割的区域内部特征具有较好的均匀性和一致性。     

A swarm intelligence approach to the quadratic minimum spanning tree problem

The quadratic minimum spanning tree problem (Q-MST) is an extension of the minimum spanning tree problem (MST). In Q-MST, in addition to edge costs, costs are also associated with ordered pairs of distinct edges and one has to find a spanning tree that minimizes the sumtotal of the costs of individual edges present in the spanning tree and the costs of the ordered pairs containing only edges present in the spanning tree. Though MST can be solved in polynomial time, Q-MST is NP-Hard. In this paper we present an artificial bee colony (ABC) algorithm to solve Q-MST. The ABC algorithm is a new swarm intelligence approach inspired by intelligent foraging behavior of honey bees. Computational results show the effectiveness of our approach.     

Topology-based image segmentation using LBP pyramids

In this paper, we present a new image segmentation algorithm which is based on local binary patterns (LBPs) and the combinatorial pyramid and which preserves structural correctness and image topology. For this purpose, we define a codification of LBPs using graph pyramids. Since the LBP code characterizes the topological category (local max, min, slope, saddle) of the gray level landscape around the center region, we use it to obtain a “minimal” image representation in terms of the topological characterization of a given 2D grayscale image. Based on this idea, we further describe our hierarchical texture aware image segmentation algorithm and compare its segmentation output and the “minimal” image representation.     

基于加权中值滤波的MST立体匹配算法

传统的最小生成树立体匹配算法对低纹理区域和遮挡区域不敏感,虽然最小生成树立体匹配算法后处理的中值滤波能够消除噪点,但是不能够消除边缘模糊。本文提出一种改进算法来克服这些局限性。首先,由于最小生成树匹配成本区分度不够高,研究并提出新最小生成树的匹配成本,使其可以减小不敏感区域的误匹配。其次,在后处理中使用加权中值滤波,以改善深度图像边缘。实验结果表明,在最小生成树立体匹配算法中使用改进匹配成本算法和加权中值滤波算法,在Middlebury数据集中平均误匹配率达到6.9%,本文算法在Middlebury和KITTI场景中都优于最小生成树立体匹配算法。     

基于最小生成树的图数据库索引算法

对复杂数据进行图模式建模近几年越来越流行,因此,在查询执行的优化过程中图索引技术变得至关重要.研究了图模式的索引问题,并且提出了一种近似的索引方法,称为MSTA方法.MSTA方法利用最小生成树结构作为索引特征,依据最小生成树边序列的包含关系和基于最大公共子图的图距离度量,将最小生成树组织到一个称为MST树的索引结构中.MST树索引结构可以高效地支持多种查询,例如子图查询.MSTA方法具备高效的索引性能.在索引大小和索引建立时间方面,传统方法是MSTA方法的数十倍,甚至上百倍.MSTA方法虽然不能返回完整结果,但是可以返回经图距离度量排序最好的部分结果.     

The equal-angle spanning tree mapping: A sequential method for projecting from h-space to 2-space

A sequential procedure for mapping the minimal spanning tree (MST) of an h-dimensional data set to 2-dimensional space is proposed. It is shown that both global and local structure are preserved well. The mapping is illustrated with the Iris data.     

Testing for uniformity in multidimensional data

Testing for uniformity in multidimensional data is important in exploratory pattern analysis, statistical pattern recognition, and image processing. The goal of this paper is to determine whether the data follow the uniform distribution over some compact convex set in K-dimensional space, called the sampling window. We first provide a simple, computationally efficient method for generating a uniformly distributed sample over a set which approximates the convex hul of the data. We then test for uniformity by comparing this generated sample to the data by using Friedman-Rafsky's minimal spanning tree (MST) based test. Experiments with both simulated and real data indicate that this MST-based test is useful in deciding if data are uniform.     

Color edge detection using the minimal spanning tree

In this study, the edge detection task in vector-valued images is examined as a clustering problem. Using samples within a data window, the minimal spanning tree (MST) provides the ordering of multivariate observations and facilitates the identification of similar classes. The edge detector parameters like edge strength, type and orientation are subsequently determined from the clustered data. Experiments and comparisons are performed, revealing the enhanced performance of the proposed approach.     

最小加权熵支撑树图像边缘提取方法

提出了一种新的彩色图像边界提取的方法,以色彩图像直方图中搜索到的峰值作为聚类中心,根据彩色图像像素结构的特点,首先计算区域内相邻像素点之间对应的向量的欧式距离,然后构造该区域内的最小支撑树,计算相应的加权熵值确定分割阈值,最后结合向量排序统计,将排序的结果按照灰度值进行分类进行输出,实验证明了这种方法的有效性。     

融合多种特征点信息的最小生成树医学图像配准

针对医学图像配准鲁棒性强、准确性高和速度快的要求,提出了一种基于融合多种特征点信息的最小生成树医学图像配准算法.该算法首先提取3种特征点,Harris-Laplace,Laplacian of Gaussian 和网格点;然后使用遗传算法去除特征点集的冗余,并通过对位映射构建无向完全图顶点集合;进而使用改进的Krusk...     

最大生成树算法和决策式算法相结合的中文依存关系解析

基于最大生成树解析算法和决策式解析算法的互补关系,提出了最大生成树解析算法和决策式解析算法相结合的中文依存关系解析方法。结合方法利用Nivre模型的依存关系解析结果和依存度修正最大生成树模型有向边的权重,再搜索最大生成树作为依存树。使用宾州中文树库中的4 500句语料作十折交叉测试,结合模型的依存关系正确率达到了86.49%。结果表明该文提出的结合方法有效地提高了的中文依存关系解析性能。     

Random-tree Diameter and the Diameter-constrained MST

A minimum spanning tree (MST) with a small diameter is required in numerous practical situations such as when distributed mutual-exclusion algorithms are used, or when information retrieval algorithms need to compromise between fast access and small storage. The Diameter-Constrained MST (DCMST) problem can be stated as follows: given an undirected, edge-weighted graph, G , with n nodes and a positive integer, k , find a spanning tree with the smallest weight among all spanning trees of G which contain no path with more than k edges. This problem is known to be NP-complete, for all values of k ; 4 h k h ( n m 2). In this paper, we investigate the behavior of the diameter of an MST in randomly generated graphs. Then, we present heuristics that produce approximate solutions for the DCMST problem in polynomial time. We discuss convergence, relative merits, and implementation of these heuristics. Our extensive empirical study shows that the heuristics produce good solutions for a wide variety of inputs.     

结合Ostu阈值法的最小生成树图像分割算法

基于最小生成树的图像分割算法是一种全局最优的算法，然而会出现图像细节的处理不甚理想的问题，即分割结果出现不同程度的过分割和欠分割的现象。针对这一现象，根据图像全局和区域间的最大类间方差（Ostu），将Ostu阈值法与最小生成树（MST）算法相结合，提出了一种基于MST的Ostu阈值法图像分割准则。该图像分割算法是一种MST的优化方法，将区域合并判决条件取决于相互合并的两个区域的Ostu阈值，又考虑到较小的区域包含在较大的目标区域中或者背景区域中，再次使用Ostu阈值进行区域合并。该方法通过实验证明，可以有效地减弱图像的过分割与欠分割比例，减少了误分割率。