• Lab 6 (14.2.2020): Cell tracking by solving the optimal assignment problem
You are given the following image files:
• “t1.png” and “t2.png” show 6 mock cell nuclei that have been generated using the algorithm discussed in the lecture (creating a wonky ellipse, adding Poisson noise, and performing a convolution with a theoretical PSF, here a simple Gaussian). They resemble two subsequent time points of an image time series.
• “t1 annotated.png” and “t2 annotated.png” show the cell centres that have been automatically detected using template matching, where the template is a disk of a size that is comparable to the nuclei. Here, a normalised cross correlation was used. Parts of a Matlab program that does the matching are shown here. The black numbers on yellow background do not reflect any correspondence between the two frames, these have just been assigned as to the order in which cell centres were found by the regionprops method.
h_width=137; % construct kernel for template matching h= z e r o s ( h _ w i d t h , h _ w i d t h ) ;
c = round(h_width/2); % define centre of disk
[X,Y] = meshgrid([1:h_width] ,[1:h_width]); % x,y coordinates for each kernel pixel r=((X−c).^2+(Y−c ).^2).^(1/2); % compute distances to centre
h(r<30)=1; % set kernel value within radius to 1
out=normxcorr2(h,img); % perform normalised crosscorrelation , % see lecture script for formula
% output needs to be cropped after the correlation [size_corr ,y]=size(out); crop=(size_corr−size_orig)/2 +[1:size_orig ]; out=out ( crop , crop ) ;
BW=out>0.45; %threshold and binarise image
s = regionprops(BW,’centroid ’); % identify individual regions of interest (ROIs) centroids = cat(1,s.Centroid); % determine centroid of ROIs
• for t1 the x,y coordinates of the cells are as follows
103.2318 103.0443 153.0704 404.2540 198.9648 290.6520 251.8117 127.3104 353.2106 352.2015 401.5475 101.9784
1
• Mean intensities for these six cells have been sampled
1703.736 2361.102 1980.235 3196.454 2894.918 1796.900
• similarly, for t2 we have x, y coordinates as follows
94.6502 223.7952 153.7713 391.7588 244.8390 293.7073 337.7024 380.5297 351.6158 185.1113 424.8356 93.8114
• and their intensities
1897.335 2801.078 2187.318 3402.642 2880.523 2303.353
a) Try to devise a mathematical formula for a suitable cost function to solve the assignment problem of matching corresponding cells in subsequent time frames of a 2D image time series. The parameters to consider are vector x, the position of cell centres, and I the average intensity of each cell. The assumption is that for a corresponding pair of cells x and I will not change drastically. Hint: The distance function used to define similarity between data points in the previous diffusion mapping might come in handy.
b) Use an implementation of the Munkres algorithm such as this one for Matlab or that one for Python.
2