Path Tracing and Computation

   An application of path tracing is intended for detecting an
external and internal borders of doubly-connected black pixels'
set (spot) and computing of spot quantitative  characteristics.
   An input converts to binarized  array  before path tracing.
   A simply-connected spot border tracing is available.
   If it is impossible to trace borders  without intersections
an output  contains  path tracing results after  elimination of
intersection points and dead ends.
   An output includes:
- a matrix with coordinates of each  spot  border  pixels;
- a matrix with the following data:
 - coordinates of points of optimal location  (centers of
   mass) for a spot and for a spot borders,
 - perimeter as length of line connecting  centers of
   borders' pixels and as a number of external (internal)
   border pixels' external (internal) edges,
 - number of  pixels in a spot and its borders,
 - coordinates of the most remote pixels for each border,
 - a distance between them,
 - coordinates of vertices of minimal  rectangle
   with a spot inside it,
 - coordinates of vertices of minimal  rectangle
   with a spot internal border inside it,
 - coordinates of  proximal  pixels and most remote ones of the
   external and internal  borders and a distance  between them,
- an array containing fragments of binarized image. They are
traced part and binarized image without this part, dead ends
and intersection points.
   Input  data might be  both an image and a numeric matrix. If
input data are a simply-connected spot a warning appears  and an
output contains data of a single border tracing.

The author - Eduard Polityko, PHD. Edition 16-Apr-2007

Displaying results

alfa='nim101.bmp';    alf1='test2_5.bmp';
alf2='nim102.bmp';    [A B]=rzrzc(alfa);
format short g;       rp=repmat('_',1,36);
cm=[0 0 0;0 0 1];
I='  Internal border - ';
E='  External border - ';
nd1=['external';'border  '];
nd2=['internal';'border  '];
nd3=['- the most   ';'remote points'];
nd4=['- center of';'border mass'];
nd5=['- center of';'spot mass  '];
nd6=['- rectangle';'vertices   '];
nd7=['- proximal';'points    '  ];
disp(rp); disp('     Coordinates')
disp('Centers of mass of contours')
disp('Center of mass of spot'); disp(B(3:4,1)')
disp('Rectangles to crop (ends of diagonal)')
disp('The most remote points of borders')
disp([E,num2str([A(B(7,1),1:2) A(B(8,1),1:2)])])
disp([I,num2str([A(B(7,2),3:4) A(B(8,2),3:4)])])
disp('  External and internal - ')
disp([A(B(4,3),1:2) A(B(5,3),3:4)])
disp('Proximal points of internal and')
disp(['external border   - ' ...
  num2str([A(B(1,3),1:2) A(B(2,3),3:4)])])
disp(rp); disp('Maximal distances between points:')
disp([E,num2str(B(9,1))]);  disp([I,num2str(B(9,2))])
disp(['  External and internal - ',num2str(B(6,3))])
disp('Distance between proximal points of')
disp(['internal and external border - ',...
disp(rp); disp('A number of black pixels:')
disp(['  Spot            - ' num2str(B(6,1))])
disp([E num2str(B(5,1))]);  disp([I num2str(B(5,2))])
disp('Perimeter as lengths of lines')
disp('connecting centers of')
disp(['  external border pixels - ',num2str(B(15,1))])
disp(['  internal border pixels - ',num2str(B(15,2))])
disp('A number of external edges')
disp(['of external border pixels - ',num2str(B(14,1))])
disp('A number of internal edges')
disp(['of internal border pixels - ',num2str(B(14,2))])
disp(rp); t2=sum(A(:,3)>0); t=sum(A(:,1)>0);

figure(2);  image(imread(alfa)); colormap(cm);  hold on;
,'w',B(4,1),B(3,1),'m*'); set(gca,'fontsize',8)
title('Doubly-connected spot','fontsize',9); grid on
'orientation','horizontal'); legend(('boxoff'));

figure(3);  plot(...
title('External border','fontsize',9);  grid on

figure(4);  plot(...
title('Internal border','fontsize',9);  grid on
for i=3:4
  figure(i);  axis ij; set(gca,'fontsize',8)
    ,'orientation','horizontal'); legend(('boxoff'))

figure(5);  axis ij;  plot(...
,[A(B(1,3),2) A(B(2,3),4)],[A(B(1,3),1),A(B(2,3),3)],'rp'...
,[A(B(4,3),2) A(B(5,3),4)],[A(B(4,3),1) A(B(5,3),3)],'rd')
title('Spot borders','fontsize',9); set(gca,'fontsize',8)
'orientation','horizontal'); legend(('boxoff'));  grid on
Centers of mass of contours
  External border - 60.9641      91.2004
  Internal border - 28.2479       94.124
Center of mass of spot
       64.655       103.04
Rectangles to crop (ends of diagonal)
  External border - 7   22  119  163
  Internal border - 13   76   45  111
The most remote points of borders
  External border - 28   22   73  162
  Internal border - 32   76   18  111
  External and internal - 
   108    36    15   108
Proximal points of internal and
external border   - 9  102   13  102
Maximal distances between points:
  External border - 147.0544
  Internal border - 37.6962
  External and internal - 117.6138
Distance between proximal points of
internal and external border - 4
A number of black pixels:
  Spot            - 8803
  External border - 474
  Internal border - 121
Perimeter as lengths of lines
connecting centers of
  external border pixels - 551.8721
  internal border pixels - 142.1249
A number of external edges
of external border pixels - 666
A number of internal edges
of internal border pixels - 168

Elimination of intersections and dead ends

figure(6);  image(imread(alf1)); colormap(cm); hold on;
[A B C]=rzrzc(alf1); t2=sum(A(:,3)>0); t=sum(A(:,1)>0);
,[A(B(1,3),2) A(B(2,3),4)],[A(B(1,3),1),...
[A(B(4,3),1) A(B(5,3),3)],'rd');  set(gca,'fontsize',8)
title('Image with border traces','fontsize',9);  grid on
legend(nd1,nd2,nd7, nd3,'location','southoutside'...
  ,'orientation','horizontal'); legend(('boxoff'))

figure(7);  image(uint8(C(:,:,2))); colormap(cm); grid on; title([...
'Image without traced part after dead ends and',...
' points of intersection elimination'],'fontsize',9);

figure(8);  image(uint8(C(:,:,1))); colormap(cm); grid on;  title(['Spot after'...
,' elimination of dead ends and points of intersection']...
,'fontsize',9); hold on;  plot(A(1:t,2),A(1:t,1),'y',...
B(1,2),'w*');set(gca,'fontsize',8); legend(nd1,nd2...
,['- external border';'  mass center    '],['- internal'...
' border';'  mass center    '],'location','southoutside'...
,'orientation','horizontal'); legend(('boxoff'))
Warning: EXTERNAL border tracing:
16 entries into dead ends were eliminated
Warning: EXTERNAL border tracing:
2 points of intersection were eliminated
Warning:  Elimination influenced upon calculation result.
Warning: INTERNAL border tracing:
3 entries into dead ends were eliminated
Warning: INTERNAL border tracing:
1 points of intersection were eliminated
Warning:  Elimination influenced upon calculation result.

Simply-connected spot path tracing

figure(9);    subplot(2,1,1);
[D F]=rzrzc(alf2);  image(imread(alf2));
set(gca,'fontsize',8); grid on; colormap(cm)
title('Simply-connected spot','fontsize',9)
subplot(2,1,2); plot(D(:,2),D(:,1),F(2),F(1),...
'b*',F(4),F(3),'m*',[F(11) F(13)],[F(10) F(12)],'o'...
,[D(F(7),2), D(F(8),2)],[D(F(7),1), D(F(8),1)],'rp')
set(gca,'fontsize',8);  grid on;  axis ij
legend(['spot  ';'border'],nd4,nd5,nd6, nd3,'location',...
'southoutside','orientation','horizontal'); legend(('boxoff'))
Warning: A spot under consideration is detected as 1-connected