[Image Processing; Edge Detection; Rule 90] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
Image Processing; Edge Detection; Rule 90
(Click here to view the original thread with full colors/images)
Posted by: Philip Ronald Dutton
Using imaging processing software (Photoshop CS in my case) I discovered that the output of the "Edge Detection" filter produces Rule 90 output for the case of an image with one line of pixels (white) and one "on" pixel (the seed cell which I made to be blue).
All I did was repeatedly apply the edge detection filter (attached in the next message is the animation of each application of the filter- chain each step's image and you will see rule 90).
Here is the link to Rule 90's output.
http://mathworld.wolfram.com/Rule90.html
The single pixel-row image that I used acts just like the cell-grid of a 1D CA. Repeated applications of the commonly available "edge detection filter" acts like the rule of a CA. The output is the same as rule 90.
Using an image of more than one row (say 300 pixels by 300 pixels) one can also seed the middle of the image with one pixel turned on. If you then repeatedly apply the edge detection filter then you will see the evolution of a 2D CA.
To fully appreciate the above phenomenon you should use your favorite imaging software.
You do not really need the imaging software unless you want to prove to yourself that Edge Detection is Rule 90 in the 1D "image" case. Just look at the Rule 90 link posted above and you can see that the Rule 90 system is detecting edges (it takes away a pixel or a group of pixels and replaces it with white space and then marks the edges by turning on cells). When the "position" of an edge is shared, there seems to be some sort of edge cancellation.
I have not checked to see how the standard edge detection algorithm is typically constructed. Regardless, the above observation is quite amazing: NKS right there under the noses of all the thousands of Image Processing users!
Posted by: Philip Ronald Dutton
Attached is the animated gif showing rule 90- the result of which was obtained by repeatedly applying the edge detection algorithm in Photoshop CS on a single pixel row which had one seed cell turned on.
(The animation is very small. It should appear at the top left of your browser frame when you click on the img link or the forum scripts will display it inline.)
Posted by: Philip Ronald Dutton
If rule 90 is an edge detector for 1D then maybe it will not be hard to find the 2D edge detector rule used by the biological eye (if the eye uses one- if not then let the robots use the rule).
Posted by: Jesse Nochella
I like your thinking!
two-dimensional nested rules could also reliably measure other things, like parallel alignment, it seems.
One other thing to take into consideration is that our brain may not process visual stimuli in a two-dimensional way. So that would mean that patches of our vision that seem far apart are actually close together.
Come to think of it, there could be many kinds of nerve topologies within the visual cortex that allow the signals from a retinal cell or elsewhere to be closer or farther apart from eachother in at different times. In other words, the actual connectivity between each spot on the visual field of the person could have a different topology than the input field, and also possibly change.
Maybe it's set up more like rings, where cells are actually more connected to cells at the same radial distance from the center of the visual field. Or maybe something like a horizontal gradient, where cells on the bottom virtually are more connected than the ones on the top. Or that all cells are more connected to the center cells than their virtual neighbors at the same radius. others??? Enumeration???
How do we get to the space of all regular lattice-like networks? gradient-ish networks?
What-else?
Posted by: Philip Ronald Dutton
Does Mathematica have some imaging routines such as "edge detection?" If so then someone should try the routine on a single pixel row image (with a center pixel turned on- given a color). Multiple applications of the filter will probably give the same output as Rule90. I have tried doing this with the GIMP and Photoshop CS and I get Rule 90.
Does anyone know what happens inside the heart of the Edge detection algorithm? It thought it used differentials, etc. I am so curious to find out why an image with a single row of pixels (white) and one on pixel (blue) would produce the Rule90 output if the underlying edge-detection algorith uses such "complicated" differentials.
Any hardcore mathematica users care to give input regarding your experience with image processing utilities of Mathematica?
Posted by: Philip Ronald Dutton
I have attached a very, very basic example of using Rule 90 as an edge detector in the context of image processing (2d, 2-color).
There are 3 items in the image. They are numbered 1, 2, and 3.
Descriptions follow:
1. This is the output of "find edges" filter in Adobe Photoshop CS using item 3 as the source image.
2. This is the result of taking vertical and horizontal "slices" (basically rows of pixels or columns of pixels) of item 3. Each slice is used as input to Rule 90 on one "step" of evolution. The output is recombined to form the image of item 2. Item 1 is a "thicker" outline than item 2. Hence, I will assume the output is less efficient than in the case of a more "strict" edge detector.
3. The source image.
Notes:
* I could have drawn a ginger-bread man (solid) and gotten the outline. The symmetry of a circular test case has no part in the experiment.
* It appears that item 2 is a "better" output than item 3 in that there are less pixels used in the output. It just seems more "uniform" and more "pleasing" to the eye.
* This technique will only work with dual color images. For images with more colors, the basic rule 90 CA can not provide an answer to the question of finding edges.
* I have not studied the standard "find edges" algorithms which, I assume, are taught in computer graphics classes in academe. I am assuming they are not based on CAs. If the standard algorithms use calculus then there is an interesting issue related to CA versus Calculus methods for finding edges. The fact that the two results shown in the attached image are so similar may suggest a connection between the two "types of mathematics."
Posted by: Chris Smeenk
Hello Phillip Dutton. You have made an interesting discovery and inspired me to check into this a little deeper. I applied your method to several of the edge detection procedures in Matlab (I hope this is not considered blasphemy by the Wolfram research people!).
The initial input in all cases consists of an 3 x L image with pixels initially set to zero. Let L = 128. The pixel value at location (2, L/2) (in this case row 2, column 64) is then set equal to one. The second row of the image is then the standard initial condition used in CAs. In creating the CAs displayed below, I have repeatedly applied the edge operator to the 3 x L image and then sampled only the second row of the image to update the CA. As Dutton noted, the process exhibits rule 90 behaviour.
It is necessary to use an input consisting of 3 rows because all the edge detection algorithms approximate the image gradient using pixel differences. These are two dimensional numerical derivatives and so the input image must also be two dimensional. Any 1D inputs do not have defined ‘edges’, according to the edge filters. I am not sure why the 1D process works on the Photoshop edge operator.
I tested six different edge operators. The simplest is ‘Roberts’ which uses only 4 pixel values (a 2 x 2 filter) to approximate a gradient (see summary by David Vernon http://homepages.inf.ed.ac.uk/cgi/r...tries.pl?TAG385 ‘Sobel’ and ‘Prewitt’ both find edges using a 3 x 3 filter, and the performance in this case resembles a rule 90 CA as noted by Dutton.
The other two similar behaviours are from the ‘Laplacian of Gaussian’ (‘log’) and ‘Zero-Crossings’ operators. These are two different operators in Matlab, however, it turns out they are equivalen under the conditions I applied them. The ‘log’ operator pre-filters an image with a Gaussian kernel of a specific standard deviation and then searches for locations where the numerical second derivative – or Laplacian – changes sign.
The last image is for the ‘Canny’ filter. This pre-filters the image with a Gaussian kernel and then uses a 3 x 3 filter to find the pixel gradients. The process is iterated with Gaussian kernels of different standard deviations.
Currently I am investigating the thresholding procedure used in the edge algorithm to suppress noisy pixels. I think this will explaing why certain CAs for the Sobel and Prewitt operators terminate at step 32.
Posted by: Chris Smeenk
Of the six edge operators I presented before Sobel, Prewitt, Laplacian of Gaussian and Zero-Crossings all terminate at the 32nd step. In these cases, the implementation of the edge detector gets confused between the real edges and its noise tolerance. The algorithm constantly makes an estimate of what edge strength a simple noisy pixel will have. It turns out at step 32, the strength of the edges in the CA falls below the set tolerance of the edge detection. Consequently the CA terminates. The Canny edge detector distinguishes between strong and weak edges and preserves weak edges only if they are connected to strong edges. This may explain why the Canny edge detector does not terminate at step 32 as most others do.
The images that follow show how different noise tolerances lead to slightly different CA behaviour. When the tolerance is set to zero, all candidate edges are accepted by the algorithm. This produces a checkerboard pattern like rules 50, 58, 110, etc. For small but non-zero thresholds, rule 90 behaviour is observed. Larger thresholds result in immediate termination of the automaton.
The edge operators themselves do not typically use a constant value as threshold, but estimate a cut-off value based on a root-mean-squared estimate of white noise. Eliminating edges with strength below the cut-off value cleans up noisy pixels which are not "true" edges.
This dynamic process can be analyzed by multiplying the cut-off value at each step by a constant weight. This is shown in the figure in the next post for different weight values. Setting the weight equal to 4 results in the CA terminating at step 32 as noted before. A weight of 3 results in the pattern terminating at step 64. For smaller weights, rule 90 behaviour continues to prevail, however, some variation in behaviour can be observed depending on the interplay between the edge locations and the ends of the automaton data (L = 128 pixels in this case).
Posted by: Chris Smeenk
this is the figure for different RMS noise cut-off weights
Posted by: Philip Ronald Dutton
In regards to my earlier post with the attached sample circle graphic, I should mention that simply taking the columns and the rows of pixels would not produce the "correct" (whatever that is) find edge result of a single source pixel. In other words, with a single pixel turned on, the method I described would not produce an edge which "fills" the boundry around that single pixel. The situation could easily be fixed by including the diagonal sequences of pixels as input to the rule 90 as well (which of course would be recombined together with the columns and rows of pixels) to form the final image. In a sense (another way to think about it), you could just take any 2d image (2 color in our case) and run rule 90 on each row saving the output. Then "rotate" the image 45 degrees so that the diagonals become rows. Run each of these new rows in the rule 90 ca and save the output. Finally "rotate" the original image another 45 degrees to get the columns as your next set of rows for input to rule 90. Combine the results again for your final output. This is all experimentation of course (yet any formalisms and bits of algorithm analysis are welcome). I will try to "foto-shop" the above process and provide a graphic representation soon.
(point 2 below contains the error mentioned above)
Originally posted by Philip Ronald Dutton
I have attached a very, very basic example of using Rule 90 as an edge detector in the context of image processing (2d, 2-color).
There are 3 items in the image. They are numbered 1, 2, and 3.
Descriptions follow:
1. This is the output of "find edges" filter in Adobe Photoshop CS using item 3 as the source image.
2. This is the result of taking vertical and horizontal "slices" (basically rows of pixels or columns of pixels) of item 3. Each slice is used as input to Rule 90 on one "step" of evolution. The output is recombined to form the image of item 2. Item 1 is a "thicker" outline than item 2. Hence, I will assume the output is less efficient than in the case of a more "strict" edge detector.
3. The source image.
Posted by: Philip Ronald Dutton
Chris,
Maybe the Photoshop programmers added extra rows in cases where the rows are less than 3. Then before displaying the result, they just crop it. I will check to see what happens if I use a 1x1 pixel image for the input to the edge filter (once with the pixel turned off and once with it on). Should be fun!
On to useful stuff:
You mention that 3 rows are used by the standard edge algorithms. Why do they use rows only? I think the column "slices" would provide useful information as well. I do not understand why only row information is used. I will, of course, have to read the algorithms but I thought I would record my question here.
Originally posted by Chris Smeenk
It is necessary to use an input consisting of 3 rows because all the edge detection algorithms approximate the image gradient using pixel differences. These are two dimensional numerical derivatives and so the input image must also be two dimensional. Any 1D inputs do not have defined ‘edges’, according to the edge filters. I am not sure why the 1D process works on the Photoshop edge operator.
Posted by: Chris Smeenk
Maybe the Photoshop programmers added extra rows in cases where the rows are less than 3
You are probably right. I suspect there is some extrapolation too.
Why do they use rows only? I think the column "slices" would provide useful information as well.
You are right here as well. There is nothing particularly significant about there being 3 rows and "L" columns - there can just as easily be L rows and 3 columns. Since cellular automata typically evolve from top to bottom, I chose the former. The edge operators work just as well in horizontal and vertical directions because images are inherently 2D.
Posted by: Philip Ronald Dutton
I was playing around with the trial edition of Mathematica (doh! It is about to expire!).
I wanted to see how the 256 elementary CAs perform as Edge Detectors.
It appears that Rule 90 is not the only rule capable of performing edge detection on a 2 color, 2d image.
I had to attach a text file with the test image and the Mathematica code since I could not save a notebook. There are probably many ways to improve my code. I just wrote this as fast as I could.
Enjoy!
Posted by: Philip Ronald Dutton
Sorry,
This is attempt #2 to attach a file.
-Philip
Posted by: Chris Smeenk
hi Philip,
which rules did you find ended up working for edge detection?
Did you give the same input as before? (i.e. a row of pixels with the middle one "on" and all the others "off")
Posted by: Philip Ronald Dutton
Sorry but my mathematica trial version has expired so I can not do anything with that code I uploaded. I did not save the images either. Basically, it was just a "smiley" face. Two solid circles for eyes and a solid mouth. I didn't have much imagination or skill to bitmap something more interesting like the shape of Italy.
Interestingly, there are some rules which give the right side edges and some which give left side edges (kind of like a shadow cast from 45 degrees left or right of the birds eye view). Maybe someone with Mathematica can run the code and post the images along with the rule number.
Posted by: Philip Ronald Dutton
Attached is an image which shows the results of using the Elem. CAs as Find Edge Filters. The left side column of images are the first half of the Elem. CAs. The right side column shows the last half. Sorry I didn't spend time with references to the rule number. When looking at the image just scroll down looking at the left side. Then scroll back up and view the right side images. That will keep you in sync with the rule numbers.
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings