무릎 자기공명영상에서 형상 사전정보 기반의 그래프 컷을 이용한 전방십자인대 분할

이한상(Hansang Lee),홍헬렌(Helen Hong),김준모(Junmo Kim) 한국정보과학회 2014 정보과학회논문지 : 소프트웨어 및 응용 Vol.41 No.1

무릎 자기공명영상에서 전방십자인대는 연골 및 후방십자인대와 같은 주변 연부조직들과 유사한 밝기값을 가지며 인접해 있어 기존의 그래프 컷과 같은 밝기값 기반의 분할을 수행할 경우 주변조직으로의 누출이 나타난다. 본 논문에서는 이러한 문제를 해결하기 위해 무릎 자기공명영상에서 형상 사전정보기반의 그래프 컷을 이용한 전방십자인대 분할기법을 제안한다. 제안방법은 두 단계로 구성된다. 첫째, 가우시안 혼합 모델 기반의 적응적 임계화와 형태학적 연산을 이용해 그래프 컷의 씨앗 정보를 추출한다. 둘째, 추출한 씨앗 정보의 형상 사전정보를 이용하여 그래프 컷을 수행, 전방십자인대 영역을 분할한다. 제안방법의 성능 평가를 위해 육안평가 및 정확성 평가를 수행하였으며, 실험결과 기존의 그래프 컷과 비교, 주변 조직으로의 누출 없이 전방십자인대의 분할 정확도가 향상된 것으로 나타났다. In this paper, we propose an anterior cruciate ligament (ACL) segmentation method in knee MR images using graph cuts with intensity and shape priors. Our method consists of two steps. First, object and background seeds for graph cuts are extracted using adaptive thresholding based on Gaussian mixture model and morphological operation on coronal and sagittal planes. Second, graph cuts are performed to segment ACL with intensity and shape priors information of extracted object and background seeds. In knee MR images, since ACL shares similar intensity with near soft tissues and some of these tissues e.g. posterior cruciate ligament (PCL) are even adjacent to ACL, leakage to these tissues occurs when an intensity-based segmentation is performed. To solve this problem, we propose the technique of representing shape priors from extracted object and background seeds, not from segmented images, and reflecting these shape priors to the graph cuts. To evaluate the performance of our method, visual inspection and accuracy evaluation were performed. Compared to the results of original graph cuts, experimental results of our method show improved segmentation accuracy without leakage into neighboring soft tissues by applying shape priors to the graph cuts.

Mean Shift 분석을 이용한 그래프 컷 기반의 자동 칼라 영상 분할 (pp.936-946)

박안진(Anjin Park),김정환(Jungwhan Kim),정기철(Keechul Jung) 한국정보과학회 2009 정보과학회논문지 : 소프트웨어 및 응용 Vol.36 No.11

그래프 컷(graph cuts) 방법은 주어진 사전정보와 각 픽셀간의 유사도를 나타내는 데이터 항(data term)과 이웃하는 픽셀간의 유사도를 나타내는 스무드 항(smoothness term)으로 구성된 에너지 함수를 전역적으로 최소화하는 방법으로, 최근 영상 분할에 많이 이용되고 있다. 기존 그래프 컷 기반의 영상 분할 방법에서 데이터 항을 설정하기 위해 GMM(Gaussian mixture model)을 주로 이용하였으며, 평균과 공분산을 각 클래스를 위한 사전정보로 이용하였다. 이 때문에 클래스의 모양이 초구(hyper-sphere) 또는 초타원(hyper-ellipsoid)일 때만 좋은 성능을 보이는 단점이 있다. 다양한 클래스의 모양에서 좋은 성능을 보이기 위해, 본 논문에서는 mean shift 분석 방법을 이용한 그래프 컷 기반의 자동 영상분할 방법을 제안한다. 데이터 항을 설정하기 위해 L<SUP>*</SUP>u<SUP>*</SUP>v<SUP>*</SUP> 색상공간에서 임의로 선택된 초기 mean으로부터 밀도가 높은 지역인 모드(mode)로 이동하는 mean의 집합들을 사전정보로 이용한다. Mean shift 분석 방법은 군집화에서 좋은 성능을 보이지만, 오랜 수행시간이 소요되는 단점이 있다. 이를 해결하기 위해 특징공간을 3차원 격자로 변형하였으며, mean의 이동은 격자에서 모든 픽셀이 아닌 3차원 윈도우내의 1차원 모멘트(moment)를 이용한다. 실험에서 GMM을 이용한 그래프 컷 기반의 영상분할 방법과 최근 많이 이용되고 있는 mean shift와 normalized cut기반의 영상분할 방법을 제안된 방법과 비교하였으며, Berkeley dataset을 기반으로 앞의 세 가지 방법보다 좋은 성능을 보였다. A graph cuts method has recently attracted a lot of attentions for image segmentation, as it can globally minimize energy functions composed of data term that reflects how each pixel fits into prior information for each class and smoothness term that penalizes discontinuities between neighboring pixels. In previous approaches to graph cuts-based automatic image segmentation, GMM(Gaussian mixture models) is generally used, and means and covariance matrixes calculated by EM algorithm were used as prior information for each cluster. However, it is practicable only for clusters with a hyper-spherical or hyper-ellipsoidal shape, as the cluster was represented based on the covariance matrix centered on the mean. For arbitrary-shaped clusters, this paper proposes graph cuts-based image segmentation using mean shift analysis. As a prior information to estimate the data term, we use the set of mean trajectories toward each mode from initial means randomly selected in L<SUP>*</SUP>u<SUP>*</SUP>v<SUP>*</SUP> color space. Since the mean shift procedure requires many computational times, we transform features in continuous feature space into 3D discrete grid, and use 3D kernel based on the first moment in the grid, which are needed to move the means to modes. In the experiments, we investigate the problems of mean shift-based and normalized cuts-based image segmentation methods that are recently popular methods, and the proposed method showed better performance than previous two methods and graph cuts-based automatic image segmentation using GMM on Berkeley segmentation dataset.

Automated Segmentation of the Lateral Ventricle Based on Graph Cuts Algorithm and Morphological Operations

Park, Seongbeom,Yoon, Uicheul The Korean Society of Medical and Biological Engin 2017 의공학회지 Vol.38 No.2

Enlargement of the lateral ventricles have been identified as a surrogate marker of neurological disorders. Quantitative measure of the lateral ventricle from MRI would enable earlier and more accurate clinical diagnosis in monitoring disease progression. Even though it requires an automated or semi-automated segmentation method for objective quantification, it is difficult to define lateral ventricles due to insufficient contrast and brightness of structural imaging. In this study, we proposed a fully automated lateral ventricle segmentation method based on a graph cuts algorithm combined with atlas-based segmentation and connected component labeling. Initially, initial seeds for graph cuts were defined by atlas-based segmentation (ATS). They were adjusted by partial volume images in order to provide accurate a priori information on graph cuts. A graph cuts algorithm is to finds a global minimum of energy with minimum cut/maximum flow algorithm function on graph. In addition, connected component labeling used to remove false ventricle regions. The proposed method was validated with the well-known tools using the dice similarity index, recall and precision values. The proposed method was significantly higher dice similarity index ($0.860{\pm}0.036$, p < 0.001) and recall ($0.833{\pm}0.037$, p < 0.001) compared with other tools. Therefore, the proposed method yielded a robust and reliable segmentation result.

그래프 컷을 이용한 학습된 자기 조직화 맵의 자동 군집화

박안진(Anjin Park),정기철(Keechul Jung) 한국정보과학회 2008 정보과학회논문지 : 소프트웨어 및 응용 Vol.35 No.9

SOFM(Self-organizing Feature Map)은 고차원의 데이타를 군집화(clustering)하거나 시각화(visualization)하기 위해 많이 사용되고 있는 비교사 학습 신경망(unsupervised neural network)의 한 종류이며, 컴퓨터비전이나 패턴인식 분야에서 다양하게 활용되고 있다. 최근 SOFM이 실제 응용분야에 다양하게 활용되고 좋은 결과를 보이고 있지만, 학습된 SOFM의 뉴론(neuron)을 다시 군집화해야 하는 후처리가 필요하며, 대부분의 경우 수동으로 이루어지고 있다. 후처리를 자동으로 하기 위해 k-means와 같은 기존의 군집화 알고리즘을 많이 이용하지만, 이 방법은 특히 다양한 모양의 클래스를 가진 고차원의 데이타에서 만족스럽지 못한 결과를 보인다. 다양한 모양의 클래스에서 좋은 성능을 보이기 위해, 본 논문에서는 그래프 컷(graph cut)을 이용하여 학습된 SOFM을 자동으로 군집화하는 방법을 제안한다. 그래프 컷을 이용할 때 터미널(terminal)이라는 두 개의 추가적인 정점(vertex)이 필요하며, 터미널과 각 정점 사이의 가중치는 대부분 사용자에 의해 입력받은 사전정보를 기반으로 설정된다. 제안된 방법은 SOFM의 거리 매트릭스(distance matrix)를 기반으로 한 모드 탐색(mode-seeking)과 모드의 군집화를 통하여 자동으로 사전정보를 설정하며, 학습된 SOFM의 군집화를 자동으로 수행한다. 실험에서 효율성을 검증하기 위해 제안된 방법을 텍스처 분할(texture segmentation)에 적용하였다. 실험 결과에서 제안된 방법은 기존의 군집화 알고리즘을 이용한 방법보다 높은 정확도를 보였으며, 이는 그래프기반의 군집화를 통해 다양한 모양의 클러스터를 처리할 수 있기 때문이다. The Self-organizing Feature Map(SOFM) that is one of unsupervised neural networks is a very powerful tool for data clustering and visualization in high-dimensional data sets. Although the SOFM has been applied in many engineering problems, it needs to cluster similar weights into one class on the trained SOFM as a post-processing, which is manually performed in many cases. The traditional clustering algorithms, such as k-means, on the trained SOFM however do not yield satisfactory results, especially when clusters have arbitrary shapes. This paper proposes automatic clustering on trained SOFM, which can deal with arbitrary cluster shapes and be globally optimized by graph cuts. When using the graph cuts, the graph must have two additional vertices, called terminals, and weights between the terminals and vertices of the graph are generally set based on data manually obtained by users. The proposed method automatically sets the weights based on mode-seeking on a distance matrix. Experimental results demonstrated the effectiveness of the proposed method in texture segmentation. In the experimental results, the proposed method improved precision rates compared with previous traditional clustering algorithm, as the method can deal with arbitrary cluster shapes based on the graph-theoretic clustering.

Segmentation for Noisy Image Based on Geodesic Distance and Graph cuts

Shanshan Gao,Jinwen Hou (사)한국CDE학회 2013 한국CAD/CAM학회 국제학술발표 논문집 Vol.2010 No.8

The paper introduces a Graph cuts method which is based on geodesic distance framework, which can achieve image denoising. A new method to compute the geodesic distance is introduced in this paper firstly, then new method combines geodesic with Graph cuts algorithm. What’s more, based on the denoising constraint, the method changes the computing method of graph’s edge weight of the image for image segmentation. This method can segment and denoise image which contains a lot of noise effectively.

Enhanced Graph-Based Method in Spectral Partitioning Segmentation using Homogenous Optimum Cut Algorithm with Boundary Segmentation

S. Syed Ibrahim,G. Ravi International Journal of Computer ScienceNetwork S 2023 International journal of computer science and netw Vol.23 No.7

Image segmentation is a very crucial step in effective digital image processing. In the past decade, several research contributions were given related to this field. However, a general segmentation algorithm suitable for various applications is still challenging. Among several image segmentation approaches, graph-based approach has gained popularity due to its basic ability which reflects global image properties. This paper proposes a methodology to partition the image with its pixel, region and texture along with its intensity. To make segmentation faster in large images, it is processed in parallel among several CPUs. A way to achieve this is to split images into tiles that are independently processed. However, regions overlapping the tile border are split or lost when the minimum size requirements of the segmentation algorithm are not met. Here the contributions are made to segment the image on the basis of its pixel using min-cut/max-flow algorithm along with edge-based segmentation of the image. To segment on the basis of the region using a homogenous optimum cut algorithm with boundary segmentation. On the basis of texture, the object type using spectral partitioning technique is identified which also minimizes the graph cut value.

Automatic Frame Composition Using Histogram Based Graph Cut

Daehee Kim,Hyungtae Kim,Jinho Park,Donggyun Kim,Joonki Paik 보안공학연구지원센터 2015 International Journal of Multimedia and Ubiquitous Vol.10 No.1

In this paper, we present an automatic background composition method using histogram-based graph cut. The proposed method consists of four steps: i) initial label map generation, ii) label map update, iii) object extraction by segmentation, and iv) dynamic background composition. Since the proposed method can minimize the user interaction for generating the initial label map and updating, it is suitable for simple interaction using a low-speed processor and limited memory space. Experimental results show that the proposed method provides better segmentation results compared with existing state-of-the-art methods with significantly reduced computational complexity. The proposed automatic object segmentation and background composition method can be applied to video editing, video conference, and video contents creation using low-cost mobile devices such as smart phones, smart TVs, and tablet PCs.

윤곽선 정보를 이용한 동영상에서의 객체 추출

김재광(Jaekwang Kim),이재호(Jaeho Lee),김창익(Changick Kim) 大韓電子工學會 2011 電子工學會論文誌-SP (Signal processing) Vol.48 No.1

본 논문에서는 객체의 윤곽선 정보에 기반한 수정된 그래프컷(Graph-cut) 알고리즘을 이용하여 동영상에서 효율적으로 객체를 추출하는 방법을 제안한다. 이를 위해 먼저, 첫 프레임에서 자동 추출 알고리즘을 이용하거나 사용자와의 상호작용을 통해 영상에서 객체를 분리한다. 객체의 형태 정보를 상속시키기 위해 이전 프레임에서 추출된 객체 윤곽선의 움직임을 예측한다. 예측된 윤곽선을 기준으로 블록 단위 히스토그램 역투영(Block-based Histogram Back-projection) 알고리즘을 수행하여 다음 프레임의 각 픽셀에 대한 객체와 배경의 컬러 모델을 형성한다. 또한, 윤곽선을 중심으로 전체 영상에 대한 로그함수 기반의 거리 변환 지도(Distance Transform Map)를 생성하고 인접 픽셀간의 연결(link)의 확률을 결정한다. 생성된 컬러 모델과 거리 변환 지도를 이용하여 그래프를 형성하고 에너지를 정의하며, 이를 최소화하는 과정을 통해 객체를 추출한다. 다양한 영상들에 대한 실험 결과를 통해서 기존의 객체 추출 방법보다 제안하는 방법이 객체를 보다 정확하게 추출함을 확인할 수 있다. In this paper, we present a method for extracting video objects efficiently by using the modified graph cut algorithm based on contour information. First, we extract objects at the first frame by an automatic object extraction algorithm or the user interaction. To estimate the objects' contours at the current frame, motion information of objects' contour in the previous frame is analyzed. Block-based histogram back-projection is conducted along the estimated contour point. Each color model of objects and background can be generated from back-projection images. The probabilities of links between neighboring pixels are decided by the logarithmic based distance transform map obtained from the estimated contour image. Energy of the graph is defined by predefined color models and logarithmic distance transform map. Finally, the object is extracted by minimizing the energy. Experimental results of various test images show that our algorithm works more accurately than other methods.

Outlier/Noise-Robust Partition of Unity Implicit Surface Reconstruction

Yukie Nagai,Yutaka Ohtake,Hiromasa Suzuki,Hideo Yokota (사)한국CDE학회 2010 한국CAD/CAM학회 국제학술발표 논문집 Vol.2010 No.8

In this paper, we propose an algorithm for outlier/noise-robust surface reconstruction based on a partition of unity (PU) approach. PU based surface reconstruction is a local method that covers an area including sampling points with spherical supports of local approximations, and then generates an approximation function whose zero-level sets approximate the surface. This algorithm has many advantages including representation of fine details, and fast and memory efficient computation. Many of these advantages are realized with the locality of PU however, it is also the reason of outlier/noise-instabilities. Unfortunately, scanned data generally contain much amount of noise, and hence improving the robustness of PU based algorithm is required. We achieve an outlier/noise-robust algorithm with integrating Graph-cut and diffusion of local approximations. Since the characteristics of outliers and noise are fundamentally different, overcoming these two with different approaches is reasonable. In our algorithm, first a spherical cover of an area containing input points is generated following the PU manner. And then Graph-cut is performed in order to determine spherical supports which are considered wrongly approximating affected by outliers. Finally, the PU approximation function is updated so that its gradient field smoothed. This smoothing is based on a diffusion of the local approximations. In this paper we show the effects of this integration approach for several scanned data sets.

Towards robust Room Structure Segmentation in Manhattan-like Environments from dense 2.5D data

Sven Olufs,Markus Vincze 제어로봇시스템학회 2011 제어로봇시스템학회 국제학술대회 논문집 Vol.2011 No.10

In this paper we propose a novel approach for the robust segmentation of room structure using Manhattan world assumption i.e. the frequently observed dominance of three mutually orthogonal vanishing directions in man-made environments. First, separate histograms are generated for the Cartesian major axis, i.e. X, Y and Z, on 2.5D data with an arbitrary roll, pitch and yaw rotation. Using the traditional Markov particle filters and minimal entropy as metric on the histograms, we are able to estimate the camera orientation with respect to orthogonal structure. Once the orientation is estimated we extract a hypotheses of the room structure by exploiting 2D histograms using mean shift clustering techniques as rough estimate for a pre-segmentation of voxels i.e. plane orientation and position. We apply superpixel over segmentation on the colour input to achieve a dense segmentation. The over segmentation and pre-segmented voxels are combined using graph-cuts for a not a-priori known number of final plane segments with a α-expansion graph cut variant proposed by Delong et al. with polynomial runtime. We show the robustness of our approach with respect to noise in real world data.