Evaluating performance of image segmentation criteria and techniques

The image segmentation problem is to delineate, or segment, a salient feature in an image. As such, this is a bipartition problem with the goal of separating the foreground from the background. An NP-hard optimization problem, the Normalized Cut problem, is often used as a model for image segmentati...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	DoritS. Hochbaum, Cheng Lyu, Erik Bertelli
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2013
Materias:	90-08 Computational methods 90B10 Network models, deterministic 90C27 Combinatorial optimization Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/e21f80da782e469eba0372d4ab2ef37f
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:e21f80da782e469eba0372d4ab2ef37f
record_format	dspace
spelling	oai:doaj.org-article:e21f80da782e469eba0372d4ab2ef37f2021-12-02T05:00:36ZEvaluating performance of image segmentation criteria and techniques2192-440610.1007/s13675-012-0002-8https://doaj.org/article/e21f80da782e469eba0372d4ab2ef37f2013-05-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000162https://doaj.org/toc/2192-4406The image segmentation problem is to delineate, or segment, a salient feature in an image. As such, this is a bipartition problem with the goal of separating the foreground from the background. An NP-hard optimization problem, the Normalized Cut problem, is often used as a model for image segmentation. The common approach for solving the normalized cut problem is the spectral method which generates heuristic solutions based upon finding the Fiedler eigenvector. Recently, Hochbaum (IEEE Trans Pattern Anal Mach Intell 32(5):889–898, 2010) presented a new relaxation of the normalized cut problem, called normalized cut′ problem, which is solvable in polynomial time by a combinatorial algorithm. We compare this new algorithm with the spectral method and present experimental evidence that the combinatorial algorithm provides solutions which better approximate the optimal normalized cut solution. In addition, the subjective visual quality of the segmentations provided by the combinatorial algorithm greatly improves upon those provided by the spectral method. Our study establishes an interesting observation about the normalized cut criterion that the segmentation which provides the subjectively best visual bipartition rarely corresponds to the segmentation which minimizes the objective function value of the normalized cut problem. We conclude that modeling the image segmentation problem as normalized cut criterion might not be appropriate. Instead, normalized cut′ not only provides better visual segmentations but is also solvable in polynomial time. Therefore, normalized cut′ should be the preferred segmentation criterion for both complexity and good segmentation quality reasons.DoritS. HochbaumCheng LyuErik BertelliElsevierarticle90-08 Computational methods90B10 Network models, deterministic90C27 Combinatorial optimizationApplied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 1, Iss 1, Pp 155-180 (2013)
institution	DOAJ
collection	DOAJ
language	EN
topic	90-08 Computational methods 90B10 Network models, deterministic 90C27 Combinatorial optimization Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90-08 Computational methods 90B10 Network models, deterministic 90C27 Combinatorial optimization Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 DoritS. Hochbaum Cheng Lyu Erik Bertelli Evaluating performance of image segmentation criteria and techniques
description	The image segmentation problem is to delineate, or segment, a salient feature in an image. As such, this is a bipartition problem with the goal of separating the foreground from the background. An NP-hard optimization problem, the Normalized Cut problem, is often used as a model for image segmentation. The common approach for solving the normalized cut problem is the spectral method which generates heuristic solutions based upon finding the Fiedler eigenvector. Recently, Hochbaum (IEEE Trans Pattern Anal Mach Intell 32(5):889–898, 2010) presented a new relaxation of the normalized cut problem, called normalized cut′ problem, which is solvable in polynomial time by a combinatorial algorithm. We compare this new algorithm with the spectral method and present experimental evidence that the combinatorial algorithm provides solutions which better approximate the optimal normalized cut solution. In addition, the subjective visual quality of the segmentations provided by the combinatorial algorithm greatly improves upon those provided by the spectral method. Our study establishes an interesting observation about the normalized cut criterion that the segmentation which provides the subjectively best visual bipartition rarely corresponds to the segmentation which minimizes the objective function value of the normalized cut problem. We conclude that modeling the image segmentation problem as normalized cut criterion might not be appropriate. Instead, normalized cut′ not only provides better visual segmentations but is also solvable in polynomial time. Therefore, normalized cut′ should be the preferred segmentation criterion for both complexity and good segmentation quality reasons.
format	article
author	DoritS. Hochbaum Cheng Lyu Erik Bertelli
author_facet	DoritS. Hochbaum Cheng Lyu Erik Bertelli
author_sort	DoritS. Hochbaum
title	Evaluating performance of image segmentation criteria and techniques
title_short	Evaluating performance of image segmentation criteria and techniques
title_full	Evaluating performance of image segmentation criteria and techniques
title_fullStr	Evaluating performance of image segmentation criteria and techniques
title_full_unstemmed	Evaluating performance of image segmentation criteria and techniques
title_sort	evaluating performance of image segmentation criteria and techniques
publisher	Elsevier
publishDate	2013
url	https://doaj.org/article/e21f80da782e469eba0372d4ab2ef37f
work_keys_str_mv	AT doritshochbaum evaluatingperformanceofimagesegmentationcriteriaandtechniques AT chenglyu evaluatingperformanceofimagesegmentationcriteriaandtechniques AT erikbertelli evaluatingperformanceofimagesegmentationcriteriaandtechniques
_version_	1718400861616472064

Evaluating performance of image segmentation criteria and techniques

Ejemplares similares