Convex Hull
By Dana Richardson
Convex Hull Defined z z
The smallest convex region enclosing a specified group of points In two dimensions, the convex hull is found conceptually by stretching a rubber band around the points so that all of the points lie within the band.
A convex shape z
A set S is convex if whenever two points P and Q are inside S, then the whole line segment PQ is also in S.
Convex Hull Masks z
There are four convex hull masks, where 1 represents black, 0 represents white and X represents a pixel that doesn’t matter, either 0 or 1.
Convex Hull Function
z
C(A) =
z
Where A represents iteratively applying the hit-or-miss transform with the 4 masks. When the masks produce no more changes, the union is performed between all 4 masks and the result becomes Di
z
Convex Hull Masks z z
z
Convex hull uses the hit or miss function If any of these masks are found in the image, then that middle pixel on the image is replaced with a 1 or black respectively. To achieve the complete convex hull image, these masks must be applied repeatedly until no further changes occur.
Convex Hull Application z
Original Black and White Image
Convex Hull Application z
Mask B1 applied to BW Image
Convex Hull Application z
Mask B2 applied to BW Image
Convex Hull Application z
Mask B3 applied to BW Image
Convex Hull Application z
Mask B4 applied to BW Image
Convex Hull Application z
Initial Result from Union
Convex Hull Application z
The Final Image with a bounding box
Convex Hull MatLab z z z
z
Useful Convex Hull MatLab functions BWHitMiss(Image,Mask) This function compares the mask to each pixel in the Image and changes the image if the mask and image match In this function -1 represents white or ‘0’, 0 represents a pixel that doesn’t matter either ‘0 or 1’, and 1 represents black or ‘1’
Convex Hull Matlab Example B1 = [1 0 0 1 -1 0 1 0 0]; z BWHitMiss(Image,B1) z Applies the mask B1 to some black and white image
MatLab Problems z
z
When applying any of the convex hull masks to a bw image, bwhitmiss assumes that all pixels outside of the image are 1 This makes the mask place 1’s all down one side of the image
Solutions z z
z
Here are two solutions to this problem. It is possible to pad a rows and columns of 0’s to the images border and only use bwhitmiss on rows and columns that are in the original image It is also possible to take the outside borders of the original image and apply them to that mask once it is completed.
Solution z
Mask Image
Original
Masked
z
Take the bottom row of the original image and replace the masked image
Convex Hull GrayScale z
z
Convex Hull does not work very well with grayscale images because it depends on the hitormiss function. The mask that you would apply would have to match the exact gray scale to get a hit.
Questions…