]> Tracer (2002-07-03)

Tracer

We've already grouped the picks into segments by looking their pairwise distances. Now we must identify the linear order of the picks within each group by some kind of line-following algorithm. We can then travel along the resulting curve, exporting 120x120 pixel image samples at regular intervals, to use in the extant reconstruction process.

Line of best fit

For starters, we'll just do regular, old-fashioned linear regression, fitting a simple line to the points of each segment. This has the fatal defect that a vertical line cannot be represented, but it's easy to implement, so we'll try it anyway as a first version.

We want to fit a line of the form $y = m x + b$ to our set of data points ${(x_{n}, y_{n})}$ . We're looking for the values of the scalars $m$ (slope) and b (y-intercept) that will minimize the aggregate squared vertical distance of points from the line ("least squares" optimisation). We can write the equation in vector form, $y = m x + b 1$ . By forming the so-called Vandermonde matrix $A = [x; 1]$ we can write the equation simply as $y = A m$ , where $m =[m b]$ :

$[\begin{matrix} y_{0} \\ y_{1} \\ ... \\ y_{n} \end{matrix}] = [\begin{matrix} x_{0} & 1 \\ x_{1} & 1 \\ ... & ... \\ x_{n} & 1 \end{matrix}] [\begin{matrix} m \\ b \end{matrix}]$

We would like to solve the equation M=A^-1y; however, in all likelihood no solution exists (the points don't actually lie on a line), so instead we solve in the "least squares sense." Matlab does this conveniently with the backslash operator (\). In Matlab we can write M = A\Y to do this.

[Micrograph with lines of best fit drawn over segments]


  % Make the Vandermode matrix

  A = ones(length(SX),2);
  A(:,1) = SX;
  
  % Solve in the least squares sense (see 'MLDIVIDE')
  
  M = A\SY; 
  
  m = M(1);  % slope
  b = M(2);  % intercept

[Micrograph with picks connected by line segments in the best fit ordering]


  u = [1 m]/norm([1 m]);        % make a unit direction vector from 'm'
  SC = (SX*u(1))+((SY-b)*u(2)); % form the dot products 

  picks = zeros(length(SC),3);  % clear/allocate the matrix
  picks(:,1) = SC;
  picks(:,2) = SX;
  picks(:,3) = SY;
  picks = sortrows(picks);      % sort by the coordinate along the line

This page is valid xhtml.
Tobin Fricke, Weizmann Institute of Science
$Id: tracer.html,v 1.1 2002/07/03 13:28:03 tobin Exp tobin $