Novel Cellular Automaton-based Image Segmentation Algorithm

This method segments an image based on the first epoch of Conway's Game of Life, with modified rules

How to cite:
author: Tyler L. Coye
date: 2015
name: Novel Cellular Automaton-based Image Segmentation Algorithm
url: https://fr.mathworks.com/matlabcentral/fileexchange/50989-novel-cellular-automaton-based-image-segmentation-algorithm
This is a fully functional and highly efficient segmentation algorithm based on the first epoch of Conway's Game of Life. To segment the 400 x 400 image depicted in the screenshot it took this algorithm 3.045760 seconds.
I used the overlay function in the script, which is not supplied in the .zip to show how the mask from the segmentation looks over the original image.
At best this is an interesting proof-of-concept that one can segment an image using cellular automatons. I did not consult the literature when writing this algorithm, so there may be a more efficient way to do it. I have gotten a lot of joy from experimenting with this algorithm and I hope you find it useful/ interesting. This may break open a new application for cellular automatons in computer vision.

In the .zip is the script for the algorithm, a padding function, and some of the output figures. The image in the screenshot is the mask from the segmentation overlayed onto the original image.

To me, the most interesting implication of this algorithm ( since it is templated on Conway's Game of Life with the only alterations being changes in epoch number and life/death rules) is that theoretically one can take any Conway Game of Life Algorithm and turn it into an edge detector after modification to the cell life/death rules and limiting the number of epochs. So, a sufficiently optimized Game of Life algorithm can become a highly robust edge detector. This area could certainly merit further research.

tic
%% Cellular Automaton-based Image segmentation Algorithm
% Copyrighted by Tyler L. Coye (2015)
%
% This was a fun little project that I have been working on. It is based on
% Conway's game of life, with minor modifications to the rules of cell
% life/death. I took any window with > 2 and <8 "alive" cells to transform
% a central pixel to "alive" regardless of its prior state. It took a
% little bit of trial and error to reach this point, but you can experiment
% with these values however you want.

% I built this from the ground up and didn't consult any prior research on
% cellular automaton image segmentation, so I am not aware of how this
% compares to other methods some may have utilized ( if it has been
% utilized at all).
%
% First read an image
I = imread('star.jpeg')
% convert it to bw (if you have not already done so)
a = im2bw(I)
% To improve processing time I have resized the image
a = imresize(a, [400 400])
sz = size(a)
epochs = 1
converged = false;
e = 1;
c = zeros(sz);
while ~converged && e<=epochs
b = zeros(sz);
a = pad( a, 2, 2);
for i=2:sz+1,
for j=2:sz+1,
w=a(i-1:i+1,j-1:j+1);
s=sum(w(:))-a(i,j);
if (s>2 && s<8) %% You can adjust these value. I found that this criteria has been suitable
b(i-1,j-1)=1;
end
end
end
figure(1);
imagesc( a);
axis image;
title( sprintf( 'original',e));
c = a;
a = b;
figure(2);
imagesc( a);
axis image;
title( sprintf( 'Epoch #%d',e));
e = e+1;
% to see what the mask looks like
figure(3);
imshow(a);
axis image;
title( sprintf( 'mask'));
end
%% to see what the overlay looks like
z = im2bw(I);
L = imresize(z, [400 400]);
out = imoverlay(L, a, [1 0 0]);
figure(4);
imagesc(out);
axis image;
title( sprintf( 'Overlay'));

toc