Prev: how to create a custom bit pattern in simulink
Next: find centroid of a moving object
From: Ashish Uthama on 28 Apr 2010 14:49
On Wed, 28 Apr 2010 16:09:05 -0300, Krishna C <chaitanya.alur(a)gmail.com>
wrote:

>
> To Ashish and Imageanalyst,
>
> Many thanks for the idea and suggestions.
>
> I implemented that flood-fill operation on the image. Its taking so much
> time to compute the result. its taking around 25min or so for the
> result. Any improvements for that flood-filling operation. The
> resolution of my image is 572*760, that give 434,720 pixels which is
> quite a big number. And checking out every pixel in the loop is taking
> more time.


Does it give you the correct answer? Have you verified the result?

It might help to post code (and the input image you use).
Others here might offer suggestions on improving the speed.


>
> As you asked, what i exactly want to compute is,
> 1. the angle of each boundary with the horizontal
> 2. the overrun of each each damage portion, i.e the ratio of A/B in the
> following image(the following image is part of the original image)
>
> http://www.flickr.com/photos/30274557(a)N05/4560719935/sizes/o/
>
> kindly have a look and give me some idea of solving this..
>
> Thank You..

From the images you have posted earlier, I cant seem to think of a robust
approach.
Have you differentiated the intersection points? (the three endpoints of
the line segments). Two of them seem easy enough (connected to the large
black blob). But I am not sure how to detect/mark the unshared end point
of line segment B.
From: ImageAnalyst on 28 Apr 2010 16:10
You might have 434,720 pixels in the entire image, but way, way less
than that in the skeleton/graph. So if you did it right, it should be
very fast. You're probably not starting from the right pixel or if
you are, you're wandering off into the background.
From: Krishna C on 29 Apr 2010 03:13
"Ashish Uthama" <first.last(a)mathworks.com> wrote in message <op.vbv1ccu4a5ziv5(a)uthamaa.dhcp.mathworks.com>...
> On Wed, 28 Apr 2010 16:09:05 -0300, Krishna C <chaitanya.alur(a)gmail.com>
> wrote:
>
> >
> > To Ashish and Imageanalyst,
> >
> > Many thanks for the idea and suggestions.
> >
> > I implemented that flood-fill operation on the image. Its taking so much
> > time to compute the result. its taking around 25min or so for the
> > result. Any improvements for that flood-filling operation. The
> > resolution of my image is 572*760, that give 434,720 pixels which is
> > quite a big number. And checking out every pixel in the loop is taking
> > more time.
>
>
> Does it give you the correct answer? Have you verified the result?
>
> It might help to post code (and the input image you use).
> Others here might offer suggestions on improving the speed.
>
>
> >
> > As you asked, what i exactly want to compute is,
> > 1. the angle of each boundary with the horizontal
> > 2. the overrun of each each damage portion, i.e the ratio of A/B in the
> > following image(the following image is part of the original image)
> >
> > http://www.flickr.com/photos/30274557(a)N05/4560719935/sizes/o/
> >
> > kindly have a look and give me some idea of solving this..
> >
> > Thank You..
>
> From the images you have posted earlier, I cant seem to think of a robust
> approach.
> Have you differentiated the intersection points? (the three endpoints of
> the line segments). Two of them seem easy enough (connected to the large
> black blob). But I am not sure how to detect/mark the unshared end point
> of line segment B.

to Ashish and ImageAnalyst:
Yeah thats the problem...time is also a constraint for me..the result should be as quick as possible..

i have the intersection points (all of them for the entire image)...but they are not in an order, all these points are saved in a matrix.. as an initial step that is what i want to do as i asked earlier...

As you said i applied flood filling algorithm..its taking much time...
kindly have a look and suggest the necessary modifications..

%% ------------------------------
clc
clear all
global A8
global r
tic
AA = [ 0 0 0 0 0 1 0 1 1 0 1;
0 1 0 1 0 0 1 0 1 1 0;
0 0 1 0 0 1 0 0 0 1 0;
0 1 0 1 0 0 1 0 0 0 1;
0 1 1 1 0 1 0 0 1 0 0;
0 0 1 0 1 0 1 1 1 0 0;
0 0 1 1 1 0 1 0 1 0 0;
0 0 0 1 0 1 1 0 0 0 0;
0 0 0 0 1 0 1 0 1 1 1; ];



AA = padarray(AA, [1 1], 0);
A8 = im2uint8(AA);
jun = [5 2;1 11;9 11]; %junction points

jun = jun+1;

for i = 1: size(jun)
A8(jun(i,1),jun(i,2)) = 2; %replace junction points with 2
end

[r,c] = size(A8);

for j = 1: length(jun)
if A8(jun(j,1),jun(j,2)) == 2

idx = (r*(jun(j,2)-1)) + jun(j,1); % to linear indices

% doing flood fill around the 8-connected neighbours of detected
% intersection. targetcolor = 255. replacementcolor = 3

FloodFill(idx+r,255, 3); %east
FloodFill(idx+r+1,255, 3); %southeast
FloodFill(idx+1,255, 3); %south
FloodFill(idx-r+1,255, 3); %southwest
FloodFill(idx-r,255, 3); %west
FloodFill(idx-r-1,255, 3); %northwest
FloodFill(idx-r,255, 3); %north
FloodFill(idx-1,255, 3); %northeast

end
end

A8(2:end-1,2:end-1)

toc

%%---------------------------------------------------------

the following is the function for FloodFill i used in the above code,

%------------------------
function FloodFill(pixelval,targetcolor, replacementcolor)
global A8
global r
A8;

if A8(pixelval) == targetcolor

A8(pixelval) = replacementcolor
FloodFill(pixelval+r,targetcolor, replacementcolor); %east
FloodFill(pixelval+r+1,targetcolor, replacementcolor); %southeast
FloodFill(pixelval+1,targetcolor, replacementcolor); %south
FloodFill(pixelval-r+1,targetcolor, replacementcolor); %southwest
FloodFill(pixelval-r,targetcolor, replacementcolor); %west
FloodFill(pixelval-r-1,targetcolor, replacementcolor); %northwest
FloodFill(pixelval-r,targetcolor, replacementcolor); %north
FloodFill(pixelval+r-1,targetcolor, replacementcolor); %northeast

end
%----------------

when i apply above to a small matrix AA..result is good and accurate but when i apply the same to the image of mine, it is taking heck of a lot of time..

i implemented the above code as you mentioned earlier...i dont understand why its taking that much time...

kindly suggest the necessary modifications..

Thank You..
From: Ashish Uthama on 29 Apr 2010 16:44
On Thu, 29 Apr 2010 04:13:03 -0300, Krishna C <chaitanya.alur(a)gmail.com>
wrote:

work in progress:

function junConMat = findConnectedJunctions(I,junPoints)
%Function to find the connected junction points.
%junConnection = findConectedJunctions(I,junPoints) returns a connectivity
%matrix. I is a binary image with 1 marking foreground. junPoints is a N
%points x 2 matrix marking the junction points. junConnection is a NxN
%matrix with a 1 in (i,j) indicating a foreground connection between
%junPoints(i,:) and junPoints(j,:) points.


%Add padding all around, udpate junction point indices correspondingly
I = uint8(I);
I = padarray(I, [1 1], 0);
junPoints = junPoints+1;
colSize = size(I,1);

junPointsLIndx = sub2ind(size(I),junPoints(:,1), junPoints(:,2));

%Mark junction points with value '2'
I(junPointsLIndx) = 2;

% no connections initially
junConMat = false([ length(junPointsLIndx) length(junPointsLIndx)]);

for jIndx = 1:length(junPointsLIndx)

curJun = junPointsLIndx(jIndx);

%Mark current point as being 'processed'
I(curJun) = 4;

%for each junction point obtain liner indices to connected junPoints
%using a Depth First Search (for connected junctions)
conJunsIndx = DFSforConJun (curJun);

%Update the connection matrix
for cIndx = 1: length(conJunsIndx)
junConMat(jIndx,...
junPointsLIndx==conJunsIndx(cIndx)) = true;
end
end

%--------------------------------------------------------------------------
function conIndx = DFSforConJun(seedJunLindx)
%Depth First Search for connected junctions. This is a nested function
conIndx=[];

%For debug
%t=I;t(seedJunLindx)=66;
%disp(t);
%pause(.5);

if(I(seedJunLindx) == 0 || I(seedJunLindx) == 3)
%we have no where to search
return;
elseif(I(seedJunLindx)==2)
%our search is done, we have found a neighbor!
conIndx = seedJunLindx;
return;
end

%continue search. Current point is either foreground(1) or seed (4)
if(I(seedJunLindx)==1)
%mark as visited
I(seedJunLindx)=3;
end

neighJunIndx = getNeighJunIndx(seedJunLindx);
for nIndx=1:length(neighJunIndx)
conIndx = [conIndx DFSforConJun(neighJunIndx(nIndx))]; %#ok<AGROW>
end
end

%--------------------------------------------------------------------------
function neighJunIndx = getNeighJunIndx(seedJunIndx)
%Return linear indices to all neighboring pixels. This is a nested
%function

%currently for 4 connected
neighJunIndx=[ ...
seedJunIndx+1, ...
seedJunIndx-1,...
seedJunIndx+colSize,...
seedJunIndx-colSize];
end

end
From: Krishna C on 2 May 2010 05:32
"Ashish Uthama" <first.last(a)mathworks.com> wrote in message <op.vbx1b2gga5ziv5(a)uthamaa.dhcp.mathworks.com>...
> On Thu, 29 Apr 2010 04:13:03 -0300, Krishna C <chaitanya.alur(a)gmail.com>
> wrote:
>
> work in progress:
>
> function junConMat = findConnectedJunctions(I,junPoints)
> %Function to find the connected junction points.
> %junConnection = findConectedJunctions(I,junPoints) returns a connectivity
> %matrix. I is a binary image with 1 marking foreground. junPoints is a N
> %points x 2 matrix marking the junction points. junConnection is a NxN
> %matrix with a 1 in (i,j) indicating a foreground connection between
> %junPoints(i,:) and junPoints(j,:) points.
>
>
> %Add padding all around, udpate junction point indices correspondingly
> I = uint8(I);
> I = padarray(I, [1 1], 0);
> junPoints = junPoints+1;
> colSize = size(I,1);
>
> junPointsLIndx = sub2ind(size(I),junPoints(:,1), junPoints(:,2));
>
> %Mark junction points with value '2'
> I(junPointsLIndx) = 2;
>
> % no connections initially
> junConMat = false([ length(junPointsLIndx) length(junPointsLIndx)]);
>
> for jIndx = 1:length(junPointsLIndx)
>
> curJun = junPointsLIndx(jIndx);
>
> %Mark current point as being 'processed'
> I(curJun) = 4;
>
> %for each junction point obtain liner indices to connected junPoints
> %using a Depth First Search (for connected junctions)
> conJunsIndx = DFSforConJun (curJun);
>
> %Update the connection matrix
> for cIndx = 1: length(conJunsIndx)
> junConMat(jIndx,...
> junPointsLIndx==conJunsIndx(cIndx)) = true;
> end
> end
>
> %--------------------------------------------------------------------------
> function conIndx = DFSforConJun(seedJunLindx)
> %Depth First Search for connected junctions. This is a nested function
> conIndx=[];
>
> %For debug
> %t=I;t(seedJunLindx)=66;
> %disp(t);
> %pause(.5);
>
> if(I(seedJunLindx) == 0 || I(seedJunLindx) == 3)
> %we have no where to search
> return;
> elseif(I(seedJunLindx)==2)
> %our search is done, we have found a neighbor!
> conIndx = seedJunLindx;
> return;
> end
>
> %continue search. Current point is either foreground(1) or seed (4)
> if(I(seedJunLindx)==1)
> %mark as visited
> I(seedJunLindx)=3;
> end
>
> neighJunIndx = getNeighJunIndx(seedJunLindx);
> for nIndx=1:length(neighJunIndx)
> conIndx = [conIndx DFSforConJun(neighJunIndx(nIndx))]; %#ok<AGROW>
> end
> end
>
> %--------------------------------------------------------------------------
> function neighJunIndx = getNeighJunIndx(seedJunIndx)
> %Return linear indices to all neighboring pixels. This is a nested
> %function
>
> %currently for 4 connected
> neighJunIndx=[ ...
> seedJunIndx+1, ...
> seedJunIndx-1,...
> seedJunIndx+colSize,...
> seedJunIndx-colSize];
> end
>
> end

%% -----

Hi Ashish,
Many many thanks for the help...

and sorry to ask this again..

when ever i use this function the MATLAB is getting crashed..

the problem its saying is
"Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit. Be aware that exceeding your available stack space can
crash MATLAB and/or your computer."

i increased the recursion limit to 5000 using,
set(0,'recursionlimit',5000)... still the problem remains same..

i tried to use the function with a small matrix of size 9x11 ... then also matlab is getting crashed..

whats to be done.. i dont find any significant portion in the code to be edited... its almost fine..
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: how to create a custom bit pattern in simulink
Next: find centroid of a moving object