Segments & Superpixels Flashcards
What is segmentation, and how does the method work?
A method to identify meaningful regions of an image and pull certain parts of interest out of the surrounding details.
Partition or group pixels according to local image properties:
Intensity or colour from original images, or computed values based on image operators
Textures or patterns that are unique to each type of region
Spectral profiles that provide multidimensional image data
What are the three types of segmentation of images?
Clustering - seeks groups of similar pixels, with no regard for where they are, views images as uncorrelated data
Region-based - Focus on finding physically connected sets of pixels e.g. region-growing, split and merge
Edge-based - Emphasise the boundaries between regions e.g. watersheds
Why was region-based segmentation created, and how does it work?
We want smooth regions in the image
Region-growing - start with a small ‘seed’ and expand by adding similar pixels
Split and merge:
Splitting divides regions that are inconsistent
Merging combines adjacent regions that are consistent
How does Region-growing work?
Starts with a small patch of seed pixels
Compute statistics about the region
Check neighbours to see if they can be added
Recompute the statistics
This procedure repeats until the region stops growing
Example - compute the mean grey level of the pixels in the region, and neighbours are added if their grey level is near the average
How does splitting work in Split and Merge?
Take the whole image to be one region
Compute some measure of similarity, and if this indicates that there is too much variety, then divide the region
Repeat this until no more splits, or we reach a minimum region size
Some details are needed however, such as standard deviations to measure similarity, or using thresholding to determine whether to split or not
What are Quadtrees?
Quadtrees are sort of like parse trees, in the sense that the root node is the entire picture, and anything chaining off of it is a quarter of the original image. This can then be split further by adding more leaf nodes, which means that that quarter of the image is yet again split into 4 quarters, each leaf node representing a section of it.
What does splitting give us when using Split and Merge?
Splitting gives us:
Regions that are small, consistent, or both
Rather too many regions, as adjacent ones may be very similar
Why should we use merging of regions in Split and Merge?
Leads to less regularly shaped regions, but they are larger and more consistent
How does merging work in Split and Merge?
Merge two regions if they are adjacent and similar
Need a measure of similarity - can compare their mean grey level, or use statistical tests
Repeat the merging until you can merge no more
How does the watershed method work?
Start by finding the image gradient, using methods like the Sobel operators, to get a value for the gradient magnitude.
Slowly ‘flood the terrain’ (terrain being image here). Flat areas of the image become areas of low gradient, whereas edges in the image have high gradient, and thus ‘split the water’.
How does the watershed algorithm work? (formal speak)
Sort the pixels - low to high
For each pixel:
If it’s neighbours are all unlabelled, give it a new label
If it has neighbours with a single label, it therefore gets that label
If it has neighbours with two or more labels, it is a watershed
What is a problem with the watershed algorithm?
It is sensitive to noise and so can generate lots of small regions
What is the efficiency of the watershed algorithm?
It is possible to implement it in O(n) time, where n is the number of pixels
This is as good as it can get, however the complexity can get to O(n log n) depending on how sorting of pixels is implemented (not sorting in linear time causes this issue)
How can you sort in linear time?
If you have a situation, whereby a large number of values exist, and those values are drawn from a small set of possibilities, you can sort in linear time with a bin
What is bin sort?
Make a bin (a list, queue, or stack) for each possible item and then, for each item:
Put it in the appropriate bin
