Achieve Computer Vision with 2DCA - 
An Introduction

Samuel Chen

Initiative in Innovative Computing, Harvard University

Abstract

Humans can easily recognize and distinguish thousands of visual categories. The best computer algorithms achieve only a fraction of human performance in terms of both the number of classes recognized and the accuracy in distinguishing between those classes. 

In this study, I have utilized 2 Dimensional Cellular Automaton (2DCA) as image sensor.  I have demonstrated that there exists a class of 2DCA that can filter horizontal, vertical and 45-degree lines among other inputs.

I have shown in this study that instead of using traditional computer algorithms for tasks such as computer vision, one can use simple programs for such concrete applications.

Introduction

Aims: In this study, I will utilize 2 Dimensional Cellular Automaton (2DCA) to serve as image sensor.

Methodology: I have tested 1,024 of 2DCA with 5 neighbors of radius 1 with different inputs to see if their behavior can be used for image sensor purposes.  The inputs include lines that are horizontal, vertical, 45-degree, angled and curved.

Result: I have found that there exists a class of 2DCA that can distinguish horizontal, vertical and 45-degree lines from any other inputs.

Initial Conditions - Lines 1

I have first introduced 4 lines that have different orientations:

Horizontal=Normal[SparseArray[{{(5|6),_}->1},{10,10}]];
Vertical=Normal[SparseArray[{{_,(5|6)}->1},{10,10}]];
lefttoright=Normal[SparseArray[{{i_,i_}->1},{10,10}]];
righttoleft=Normal[SparseArray[{{i_,j_}/;i+j===11->1},{10,10}]];
Show[GraphicsArray[Map[ArrayPlot[#,DisplayFunction->Identity]&,{Horizontal,Vertical,lefttoright,righttoleft}]]]

Initial Conditions - Lines 2

I have in this section introduced lines that are at an angle, and curved lines：

grline1=Graphics[Line[{{0,0},{7,80}}]];
	rasline1=ImportString[ExportString[grline1,"GIF",ImageSize->15],"GIF"][[1]];
		line1=Reverse[1-rasline1[[1]]];

grline2=Graphics[Line[{{0,0},{-7,80}}]];
	rasline2=ImportString[ExportString[grline2,"GIF",ImageSize->15],"GIF"][[1]];
		line2=Reverse[1-rasline2[[1]]];

grline3=Graphics[Line[{{0,0},{-7,-80}}]];
	rasline3=ImportString[ExportString[grline3,"GIF",ImageSize->15],"GIF"][[1]];
		line3=Reverse[1-rasline3[[1]]];

grline4=Graphics[Line[{{0,0},{7,-80}}]];
	rasline4=ImportString[ExportString[grline4,"GIF",ImageSize->15],"GIF"][[1]];
		line4=Reverse[1-rasline4[[1]]];

grcurveline=Graphics[Text["(",{0,0}],DefaultFont->{"Courier",10.}];
	rascurveline=ImportString[ExportString[grcurveline,"GIF",ImageSize->15],"GIF"][[1]];
		curveline=Reverse[1-rascurveline[[1]]];

Show[GraphicsArray[Map[Graphics,{rasline1,rasline2,rasline3,rasline4,rascurveline}]]]

Initial Results

All 1,024 5 neighbor rules have been tried.  I have visualized all the results.

Initial Condition - Lines 1:

Result of initial condition - Lines 1:

Type 1: The 2DCA are dependant upon the orientation of the line:

Type 2: The 2DCA that are independent of the orientation of the line, yet all cells become filled:

Type 3: The 2DCA that are independent of the orientation of the 45 degrees lines, yet dependant upon the horizontal and vertical lines:

Type 4: The 2DCA that are independent of the orientation of the horizontal and vertical lines, yet dependant upon the 45 degrees lines:

Type 5: The 2DCA seem to "multiply" the horizontal and vertical lines, however, they are independent to the 45 degrees lines:

Type 6: The 2DCA seem to "multiply" the horizontal and vertical lines, yet, they are also dependant upon the 45 degrees lines:

Type 7: The 2DCA seem to "multiply" the 45 degrees lines, however, they are independent to the vertical and horizontal lines:

Type 8: The 2DCA seem to "multiply" the 45 degrees lines, yet, they are also dependant upon the vertical and horizontal lines:

Type 9: The 2DCA seem to "multiply" all 4 inputs:

Further Investigation - Multiplication of Lines

One interesting aspect of the above results is the "multiplication" of lines.  One might think that if one runs the 2DCA for 10 steps, the lines are multiplied, if one runs the same rule for a longer steps, the result might be different.  However, this is not the case.

10 Steps:

1,000 Steps:

10,000 Steps:

1,000,000 Steps:

Initial Conditions - More Lines

Let's focus upon lines that are at an angle and lines that are considered curved to test 2DCAs.

Initial Condition:

Type 1: The 2DCA seems to reflect what is given as input:

Type 2: The 2DCA seems to reflect "hints" of what is given as input but shown in an abstract way:

Type 3: The 2DCA evolves the input into smeared unrecognizable pattern with 10 steps:

Rule 805's output remain even after 100,000 steps:

Concrete Result

Filter 1: They distinguish horizontal, vertical vs. others.

I have also found 2 other rules that will serve the same purpose but with different colored outputs.

SelectionResult=Select[Allruledata,#[[2]]<.01&&#[[3]]<.01&&#[[4]]<.01&&#[[5]]<.01&&#[[6]]>.5&&#[[7]]>.5&&#[[8]]>.5&&#[[9]]>.5&&#[[10]]>.5&&#[[11]]>.5&&#[[12]]>.5&];

Filter 2: They distinguish horizontal, vertical and 45 degree lines vs. others

SelectionResult=Select[Allruledata,#[[2]]>.99&&#[[3]]>.99&&#[[4]]>.99&&#[[5]]>.99&&#[[6]]>.99&&#[[7]]>.99&&#[[8]]<.9&&#[[9]]<.9&&#[[10]]<.9&&#[[11]]<.9&&#[[12]]<.9&]

Meet the winners:

Filter 1:

Manipulate[Table[ArrayPlot[CellularAutomaton[{n,{2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},{{{m}}}]],{n,{58,122,181,189,245,253,314,376,437,445,501,509}}],{m,1,25,1}]

Manipulate[Table[ArrayPlot[CellularAutomaton[{n,{2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},{{{m}}}]],{n,{660,724}}],{m,1,25,1}]

Filter 2:

Manipulate[Table[ArrayPlot[CellularAutomaton[{n,{2,{{0,2,0},{2,1,2},{0,2,0}}},{1,1}},{{{1}},0},{{{m}}}]],{n,{183,247,439,503}}],{m,1,50,1}]

Conclusion and Further Applications

Current state of computer vision technology is not sufficient to serve as an efficient tool that is readily available as an off-the-shelf package.  In this study, I have demonstrated that we can utilize simple programs such as 2 dimensional cellular automata to serve as a filter.  This class of filters shows great promise of being used as the underlying technology for future generation of computer vision software.

The particular class of 2DCA filters vertical, horizontal and 45-degree lines only and for no other inputs.  This short program serves as a foundation for the study of utilizing of simple programs to identify images, which furthers the study of computer vision. 

One of the most immediate applications of such filters is to differentiate a true signal vs. noise.  For instance, with time series analysis, one has a collection of tools that can be used to achieve such a task.  Tools include Fourier transforms, wavelets, scan statistics and many more.  With the investigation of 2DCA, one would hope that simple programs can be included into investigators' tool box.