A Fast Image Segmentation using Delaunay Triangulation

A fully automated process that does not require initial estimate of number of clusters.
9.3K Downloads
Updated 6 Aug 2011

View License

This function applies the Delaunay-based image segmentation, which is a fully automated process that does not require initial estimate of number of clusters.

The core idea is to apply Delaunay triangulation to the image histogram instead of the image itself. That reduces the sites required to construct the diagram to merely 255 at most (uint8) resulting in a fast image segmentation.

I don't claim it is the optimal way to segment an image, which is why I will be more than happy receiving constructive comments or reporting any bug in the program for further improvement.

For a detailed description of the theoretical foundation of the algorithm and for citation purposes please refer to the journal paper -a pre-print copy is included here but it is better to have it in PR layout-:

- A. Cheddad, D. Mohamad and A. Abd Manaf, "Exploiting Voronoi diagram properties in face segmentation and features extraction," Pattern Recognition, 41 (12)(2008)3842-3859, Elsevier Science.
- A. Cheddad, J. Condell, K. Curran and P. Mc Kevitt. On Points Geometry for Fast Digital Image Segmentation. The 8th International Conference on Information Technology and Telecommunication IT&T 2008, Ireland 23 – 24 October 2008, pp: 54-61.

Example:
[Segmented, Array]=DS(Im);
[Segmented, Array]=DS(Im,flag,open,EdHist);

Inputs,
Im : The image, class preferable uint8 or uint16, the function
accepts RGB as well as grayscale images

flag : (1) segmentation of image complement
(0) direct segmentation [default]

open: (1) apply grayscale morphological opening
(0) don't apply [default]

EdHist:(1) apply histogram equalization [default]
(0) don't apply

Outputs,
Segmented: the segmented image
Array: Array containing grayscale values (Delaunay vertices)
used for segmentation. You can use that to call homogeneous
regions,

e.g., imshow(Segmented(:,:,1)==Array(i),[]); %for gray scale

or Segmented_ntsc=rgb2ntsc(Segmented);
imshow(Segmented_ntsc(:,:,1)<=Array(i) &
Segmented_ntsc(:,:,1)>Array(i-1),[]); %for colour images
Note: NTSC transformation will introduce some changes to
values in the vector Array.

Cite As

Abbas Cheddad (2024). A Fast Image Segmentation using Delaunay Triangulation (https://www.mathworks.com/matlabcentral/fileexchange/28330-a-fast-image-segmentation-using-delaunay-triangulation), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2010a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.22.0.0

Some bugs in displaying the values in "Array" have been fixed.

1.21.0.0

- A user friendly GUI creation
- Now the programme exports the segmented image as "Segmented.tif"

1.19.0.0

Updated description and screenshot

1.17.0.0

Updated screen shot and description

1.13.0.0

Update to description and screen shot

1.10.0.0

- Bug fix (gray colour count in RGB)
- Appended a new screenshot
- Added some useful comments to the script

1.8.0.0

Bug fixed (grayscale count for RGB images) and file script update

1.4.0.0

Mistake at the end of the script.

if length(size(Im))==3
Im(:,:,1)=im2double(Orig);
Orig=ntsc2rgb(Im);
[x xx]=imhist(Im(:,:,1));
xx(x==0)=0;
Array=xx(xx>0);
else
[x xx]=imhist(im2uint8(Orig(:,:,1)));
xx(x==0)=0;
Array=xx(xx>0);
end

1.1.0.0

Revised the description and added some tags.

1.0.0.0