By -

## Convex Hull:

Consider a set S its convex hull would be a set H such that if we join any two points of set H with a straight line this straight line lies entirely in H. This convex hull H of set S is the smallest convex set that contains S in it. The set obtained by difference of these two sets(H-S) is called the “Convex Deficiency” of set S.

A convex hull describes an object its orientation in an image which can be very useful in image processing. As an object may have different convex hull sets with respect to its different orientations in an image and the areas of sets obtained from these orientations of an object can tell us that in what position or orientation is placed in that image.

### Algorithm for Convex Hull:

Step 1. Let Bi, i=1,2,3,4, represent four structuring elements shown in figure below. The origin of all these elements is at centre and ‘x’ represents ‘don’t-care’ conditions. It means that for a match the centre pixel of these elements needs to be at 0 pixel of the region of image the mask is placed on and the shaded pixel of element be masking 1 on the image region behind.  The ‘x’ pixels are don’t care whether they are at 1 or 0. You can see that if we rotate B1 clockwise by 90 degrees it will become B2 and rotate B2 by 90 degrees clockwise will give B3 and so on. We can write Bi=clockwise 90 degrees rotation of Bi-1.

Step 2. The procedure consists of applying hit-or-miss transform to set A(the image) iteratively with element B1 as long as no changes occur, then we perform union with A and store as D1. We then repeat this same procedure with B2 until no changes occur and store it in D2. We do this same step with remaining 2 elements B3 and B4 and store the result in D3 and D4 respectively.

Step 3. We then take union of all these D’s which will give us the convex hull of set A(the image).

### Note:

The hit-miss transform used in this procedure we don’t use background. If you want to learn about hit-miss transform and its code for Matlab click here.

## Matlab Code:

### Note:

The image ‘impcon.bmp’ needed for proper execution of this code as this image is read in this code.To get it click here

Doing Computer Engineering and love programming, helping others out and providing solutions to problems....

### 1 Comment to Convex Hull Matlab Code And Explanation

1. CAN U EXPLAIN THIS CODE PLZ
function [ match num] = SIFTMatch(im1, des1, loc1, im2, des2, loc2)
distRatio = 0.6;
matched_points_img1 =[];
% For each descriptor in the first image, select its match to second image.
des2t = des2′; % Precompute matrix transpose
for i = 1 : size(des1,1)
dotprods = des1(i,:) * des2t; % Computes vector of dot products
[vals,indx] = sort(acos(dotprods)); % Take inverse cosine and sort results
% Check if nearest neighbor has angle less than distRatio times 2nd.
if (vals(1) 0);
final_match = zeros(1,length(match)); % if == 1, the corresponding match(i) is accepted. if ==0, the corresponding match(i) is rejected
dis_img_1= zeros(num ,num); % each row contains the spatial distance vector that descript the correctness of the point
dis_img_2= zeros(num ,num);

orien_diff_img_1= zeros(num ,num); % each row contains the orientation difference vector that descript the correctness of the point
orien_diff_img_2= zeros(num ,num);
for k = 1: num
dis_img_1(k, k) = 0;
dis_img_2(k, k) = 0; % the distance between the point and distance is 0

orien_diff_img_1(k,k) = 0;
orien_diff_img_2(k,k) = 0;

for j = k+ 1: num
dis_img_1(k, j) = sqrt( (loc1(matched_points_img1(k), 1) – loc1(matched_points_img1(j), 1))^2 …
+ (loc1(matched_points_img1(k), 2) – loc1(matched_points_img1(j), 2))^2 );
dis_img_1(j, k) = dis_img_1(k, j); % dis_img_1 is a symmetric matrix

% compute the corresponding distances of the matching points in
% image 2
dis_img_2(k, j) = sqrt( ((loc2(match(matched_points_img1(k)), 1) – loc2(match(matched_points_img1(j)), 1))^2 + (loc2(match(matched_points_img1(k)), 2) – loc2(match(matched_points_img1(j)), 2))^2 ));
dis_img_2(j, k) = dis_img_2(k, j); % dis_img_1 is a symmetric matrix

orien_diff_img_1(k, j) = loc1(matched_points_img1(k), 4) – loc1(matched_points_img1(j), 4);
orien_diff_img_1(j, k) = orien_diff_img_1(k, j); % dis_img_1 is a symmetric matrix

orien_diff_img_2(k, j) = loc2(match(matched_points_img1(k)), 4) – loc2(match(matched_points_img1(j)), 4);
orien_diff_img_2(j, k) = orien_diff_img_2(k, j); % dis_img_1 is a symmetric matrix

end
end

% normalize the distance and orein_diff vector
for ii =1: num
dis_img_1(ii, = dis_img_1(ii, ./ norm(dis_img_1(ii, );
dis_img_2(ii, = dis_img_2(ii, ./ norm(dis_img_2(ii, );

orien_diff_img_1(ii,:) = orien_diff_img_1(ii,:) ./( eps + norm(orien_diff_img_1(ii,:)));
orien_diff_img_2(ii,:) = orien_diff_img_2(ii,:) ./( eps +norm(orien_diff_img_2(ii,:)));

end

for m = 1: num
dis_coherence = dot(dis_img_1(m,:), dis_img_2(m,:));
orein_coh = dot(orien_diff_img_1(m,:), orien_diff_img_2(m,:));
if dis_coherence > dis_thres && (orein_coh > orien_thres || ( sum(orien_diff_img_1(m,:)>0) == 0 && sum(orien_diff_img_2(m,:)>0) == 0 ) )
% if the orientations are the same, then orein_coh will be 0, so
% cope with this with another condition
final_match(matched_points_img1(m)) = 1;
end
end

match = match .* final_match;
num = sum(match > 0);
fprintf(‘Found %d matches.\n’, num);

% Create a new image showing the two images side by side.
im3 = SIFTUTILAppendimages(im1,im2);

% Show a figure with lines joining the accepted matches.
figure,imshow(im1);title(‘Reference Image’);
hold on
loc1 = ceil(loc1);
loc2 = ceil(loc2);
cols1 = size(im1,2);
for i = 1: size(des1,1)
plot(loc1(i,1),loc1(i,2),’r*’);
end
hold off
figure,imshow(im2);title(‘Test Image’);
hold on
% cols1 = size(im1,2);
for i = 1: size(des2,1)
% plot(loc2(i,1),loc2(i,2),’r*’);
plot(loc2(i,1),loc2(i,2),’r*’)
end
hold off
figure(‘Position’, [100 100 size(im3,2) size(im3,1)]);
colormap(‘gray’);
imagesc(im3);
hold on;
cols1 = size(im1,2);
%for i = 1: 374
%num
for i = 1: size(des1,1)
if (match(i) > 0)
line([loc1(i,1) loc2(match(i),1)+cols1], …
[loc1(i,2) loc2(match(i),2)], ‘Color’, ‘c’);
end
end
hold off;

% match = match .* final_match;
% num = sum(match > 0);
% fprintf(‘Found %d matches after refinement.\n’, num);
%
% % % Show a figure with lines joining the accepted matches.
% figure(‘Position’, [100 100 size(im3,2) size(im3,1)]);
% colormap(‘gray’);
% imagesc(im3);
% hold on;
% cols1 = size(im1,2);
% for i = 1: size(des1,1)
% if (match(i) > 0)
% line([loc1(i,1) loc2(match(i),1)+cols1], …
% [loc1(i,2) loc2(match(i),2)], ‘Color’, ‘c’);
% end
% end
% hold off;