Image Segmentation

 

Introduction                                                                                                                                                                                                                                            

The segmentation problem                                                                                                                    

Image segmentation is a process in which regions or features sharing similar characteristics are identified and grouped together, The output of the segmentation step is usually a set of classified elements.

Most segmentation techniques are either region-based or edgebased.

  • Region-based techniques rely on common patterns in intensity values within a cluster of neighboring pixels. The cluster is referred to as the region, and the goal of the segmentation algorithm is to group regions according to their anatomical or functional roles.
  • Edge-based techniques rely on discontinuities in image values between distinct regions, and the goal of the segmentation algorithm is to accurately demarcate the boundary separating these regions.

my goal:                                                                                                                                                    

My goal in this work to implement  "graph based image segmentation" algorthim.

The workflow:                                                                                                                                           

The following diagram explains my workflow in a very high level

The algortim:                                                                                                                                           

 

 

The input is image (RGB/Gray) ,next build a graph G = (V;E), with n vertices(pixels of the image) and m edges(between each tow neighbor pixels) .

The output is asegmentation of V into components S = (C1;......;Cr).

 

 

moving to the algorthim code with example:

 

input image:


paramter:

 sigma = 0.8  #for gaussian mask     

 K = 600      # threshold 

 

 

 

step 1:

filter the image with gaussain mask (sigma 0.8)

 

I use a Gaussian filter to smooth the image slightly before computing the edge weights, in order to compensate for digitization artifacts.I always use a Gaussian with sigma = 0.8, which does notproduce any visible change to the image but helps remove artifacts.

 

 

step 2:

 

build the graph,

i define an undirected graph G = (V,E), where each image pixel pi has a corresponding vertex vi Ε V .The edge set E is constructed by connecting pairs of pixels that are neighbors in an 8-connected sense . This yields a graphwhere m = O(n), so the running time of the segmentation algorithm is O(n log n)for n image pixels.

i use an edge weight function based on the absolute intensity defierence between the pixels connected by an edge,w((vi, vj)) = |I(pi) - I(pj)|

 

 

step 3:

 

Sort the graph for each color

Example for Red color sorted graph:


 

step 4:

 

init forest for each color, each vertix(i) is a segment with size 1,rank=1,parent=i;

 

from q=1 to q=m;

do:

 

The gaurd image with Red color segmentaion

The gaurd image with Blue color segmentaion

The gaurd image with Green color segmentaion


step 5:


we put two neighboring pixels in the same component when they appear in the same component in all three of the color plane segmentations.

 

 

step 6 (extra):

 

 

merge conponents that user choose 

input pic for choosing component to merge

 

result :

 

another function:

merge small comp' if there size is small than paramter comp_min_size

result:


 

More examples:

result in gray image                        

 

 

 

result for RGB images             


first image= the orginal image

second image = segment image without removing small conponents

 

 

 

 

 

 

 

 

 

Related files:                                                                                                                                          

The code available here

Cridet:                                                                                                                                          

This project was prepared by Majed Abu Mokh, student for B.Sc. degree in Computer Science in University of Haifa, Israel, as an assignment in the course Computre-vision, taught by Dr. Daniel Keren, 2016