title: Joint graph cut and relative fuzzy connectedness image segmentation algorithm.
abstract: We introduce an image segmentation algorithm, called GC(sum)(max), which combines, in novel manner, the strengths of two popular algorithms: Relative Fuzzy Connectedness (RFC) and (standard) Graph Cut (GC). We show, both theoretically and experimentally, that GC(sum)(max) preserves robustness of RFC with respect to the seed choice (thus, avoiding "shrinking problem" of GC), while keeping GC's stronger control over the problem of "leaking though poorly defined boundary segments." The analysis of GC(sum)(max) is greatly facilitated by our recent theoretical results that RFC can be described within the framework of Generalized GC (GGC) segmentation algorithms. In our implementation of GC(sum)(max) we use, as a subroutine, a version of RFC algorithm (based on Image Forest Transform) that runs (provably) in linear time with respect to the image size. This results in GC(sum)(max) running in a time close to linear. Experimental comparison of GC(sum)(max) to GC, an iterative version of RFC (IRFC), and power watershed (PW), based on a variety medical and non-medical images, indicates superior accuracy performance of GC(sum)(max) over these other methods, resulting in a rank ordering of GC(sum)(max)>PW∼IRFC>GC.
authors.affiliation: Department of Mathematics, West Virginia University, Morgantown, WV 26506-6310, United States; Department of Radiology, MIPG, University of Pennsylvania, Blockley Hall, 4th Floor, 423 Guardian Drive, Philadelphia, PA 19104-6021, United States. Electronic address: KCies@math.wvu.edu.
authors.forename: Krzysztof Chris
authors.initials: KC
authors.lastname: Ciesielski
authors.forename: Paulo A V
authors.initials: PA
authors.lastname: Miranda
authors.forename: Alexandre X
authors.initials: AX
authors.lastname: Falcão
authors.forename: Jayaram K
authors.initials: JK
authors.lastname: Udupa
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D017143:Fuzzy Logic; D007089:Image Enhancement / Q000379:methods; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D013382:Subtraction Technique
keywords: Fuzzy connectedness; Graph cut; Image segmentation; Robustness