Removing equidistant points from an image
I have this image -
I want to delete this point marked with yellow circles,
So basically I want to remove all those points that are almost equidistant and lie almost on the same line between any two points.
This is what I have tried. I found the equation between any two points and deleted all the points that lie on that line. Here is what I have tried -
clc;
I=imread('untitled.png');
imshow(I);
I=im2bw(I);
L = bwlabel(I,8) ; %Calculating connected components
mx=max(max(L));
for i=1:mx
[r1,c1] = find(L==i);
x1=mean(c1);
y1=mean(r1);
for j=1:mx
if i~=j
[r2,c2] = find(L==j);
x2=mean(c2);
y2=mean(r2);
slope=(y2-y1)./(x2-x1);
for k=1:mx
[r,c] = find(L==k);
rc = [r,c];
x3=mean(c);
y3=mean(r);
temp=((y3-y2)-(slope).*(x3-x2));
if k~=i & k~=j
if temp >=-0.5 & temp <=0.5
for l=1:r
for m=1:c
I(l,m)=0;
end
end
end
end
end
end
end
end
figure,imshow(I);
But here it will remove all points that lie on the line, not just at equidistant points. Also, the time complexity is O (N ^ 5), so this algorithm will not work even for small values. don't check my code above for input image on condition that it takes too long. So, can I do this?
source to share
Not only is your code O (n ^ 5), but the commands find
in particular are very slow.
I think you can do this easily in O (n ^ 3) with minimal use of commands find
.
It will look like this:
1) Create an Nx2 point array by reducing the image to a series of data points.
nPoints = max(L(:)); points = zeros(nPoints, 2); for ix = 1:nPoints [r1,c1] = find(L==ix); points(ix,:) = [r1,c1]; end
It should be very fast.
2) Now, for each point, check if it is almost between two other points.
maskRemove = false(nPoints,1);
for ixPoint = 1:nPoints
for ixEndA = 1:nPoints
for ixEndB = 1:(ixEndA-1) %We don't need to check both directions
rcCheck = points(ixPoint,:);
rcEndA = points(ixEndA ,:);
rcEndB = points(ixEndB ,:);
%We want to see if the "check" point is near the average
%of the endpoints
meanOfEnds = mean([rcEndA; rcEndB], 2);
%This is a MAX norm, you can use a circular distance
%check if you want.
distanceFromMean = max(abs(meanOfEnds - rcCheck ) );
%Mark the result in the results mask
maskRemove(ixPoint)= distanceFromMean < thresholdValue;
end
end
end
%Now, "maskRemove" should be a logical TRUE for any point that needs
%to be removed.
source to share
I think a good way to do it is to do it. It ~ O (N) with the number of circles
>> TimingFunction(1000, 2)
Elapsed time is 0.103834 seconds.
>> TimingFunction(1000, 4)
Elapsed time is 0.179529 seconds.
>> TimingFunction(1000, 8)
Elapsed time is 0.270225 seconds.
>> TimingFunction(1000, 16)
Elapsed time is 0.601423 seconds.
>> TimingFunction(1000, 32)
Elapsed time is 1.070139 seconds.
And O (N ^ 2) with image size (I used square for test)
>> TimingFunction(500, 16)
Elapsed time is 0.139831 seconds.
>> TimingFunction(1000, 16)
Elapsed time is 0.531034 seconds.
>> TimingFunction(2000, 16)
Elapsed time is 1.974798 seconds.
And the function:
function TimingFunction(SquareSize, NumberCircles)
%This is generating a sample "image"
I = ones(SquareSize);
%This is generating sample circles
X = randi(round(0.9*size(I, 2)), NumberCircles, 1);
Y = randi(round(0.9*size(I, 1)), NumberCircles, 1);
R = randi(round(min(size(I)) / 20), NumberCircles, 1);
%this is timing
tic
Ip = circleErase(I, X, Y, R);
toc
%Just to allow for visualization
surf(Ip)
end
%this is the actual code
function I = circleErase(I, X, Y, R)
%I is the image, if it RGB rather than a matrix you will need to modify the last line slightly
%X is a vector of the x coordinates of the center of the circle
%Y is a vector of the y coordinates of the center of the circle
%R is a vector of the circles radii
%Assign x,y coordinates to each point
[GridX, GridY] = meshgrid(1:size(I, 2), 1:size(I, 1));
%Want points within 1 unit
Within = 1;
%Finds the points within one unit for each circle edge
closeEnough = arrayfun(@(x, y, r) abs(r - sqrt((x - GridX).^2 + (y - GridY).^2)) <= Within, X, Y, R, 'uni', 0);
%Changes from a cell array to a 3D array (using:
% http://www.mathworks.com/matlabcentral/answers/35766-cell-array-into-3d-matrix)
% then finds if points intersect with any of the circles
eraseIt = any(permute(reshape(cell2mat(closeEnough).',size(closeEnough{1}, 1),size(closeEnough{1},2),[]),[3 2 1]), 1);
%Then erases it
I(eraseIt) = 0;
end
source to share