Continuous Edge Tracking

[Katie_Lab4]

Hello LabVIEW! 

My problem is I have a 2d array of data values, which should all be relatively low. I want to be able to create a VI that counts how many values greater than my threshold (lets say 3) are "touching". By touching, I mean either to the left, right, top, bottom, or any diagonal of that current value. If there is a touching, or neighboring value, I then want it to move on to that value, and then tell if there are any neighboring values to that value that are over the threshold as well. Essentially, I want this process to continue until there are no more neighboring values over that threshold, and the VI will tell me how many values over that threshold were touching. 

To give a little background on what I am doing, I have created a VI where it will take a 2d array of what we will call "Normalized Data", and it iterates through each value and creates a pixel neighborhood (the surrounding 8 pixels).It then calculates the standard deviation of that pixel neighborhood, and outputs a new 2d array of all the standard deviations for each pixel neighborhood in the original 2d array. If the std dev is above a certain threshold, that qualifies as an "edge" in the data. Now I want to determine how big (or how many values) makeup the largest edge. 

[Bob_Schor]

Hello, Katie.  An interesting problem that (to me) says "You may want a recursive algorithm".

If I were trying to do this, I would start with (maybe Graph) paper and pencil and think about this problem a bit.  Let's call the elements of the 2D array "Pixels" (note that this may suggest that you've stumbled upon a "solved problem" known to people doing Image Analysis, not my field of expertise), and let's call its dimensions M x N.  The first thing I'd do is to create an array of "Thresholded Pixels", an M x N array of Booleans, True if the value > Threshold.  I'd surround this M x N array with a 1D Array of "sub-threshold" cells to create a "edge" (otherwise you are computing on a toroidal surface), resulting in an M+2 x N+2 Boolean Array.

Now you simply (Famous Last Words) start "marking" regions.  Here's where the recursion comes in.  Take a Cell you haven't looked at yet (how do you know you haven't looked at it?  You might need to add a "marker" to say "Already Looked At", suggesting the Cell needs another Boolean value, suggesting a Cluster?).  If all its surrounding 8 Cells are sub-threshold, you've determined its size (namely "1").  Otherwise, its size will be 1 + sum (sizes of surrounding Cells, taking care not to count Cells Already Looked At).

Play with that a bit on paper.  Now think about translating it to LabVIEW.  Do you know how to write Recursive VIs with LabVIEW?  It's basically going to the VI Properties, Execution, and setting it to "Shared Clone Reentrant".  Once you have done this, you can call the VI from within itself.

Have fun.  If you start, and get stuck, come back here and Post your VI (we'll want to be able to execute it, which we can't do with a picture).  I hope my Learned Colleagues will allow you some time to play with this yourself, rather than rush to Post the Solution, as this is a great Opportunity to Learn.

Bob "I love Recursion" Schor

[Katie_Lab4]

Thank you so much for your response! So far I have created a VI that takes an MxN dimension array, replaces all the values over a certain threshold with a Boolean value of 1 and all the values sub-threshold with a Boolean value of 0. I have also made it so a 3x3 subarray is created (that represents the pixel neighborhood), where it places the current pixel in the center of the subarray, and creates an outer edge of 0s (if you are at an edge in the input array). 

Right now where I'm stuck is the "marking" section. So, ideally, each pixel will be "marked" as seen once the code iterates through it. If the current pixel is greater than the threshold, it will create the "pixel neighborhood" around it and check if those values are greater than the threshold. If they are, it will add them to an "island" and go back to iterating through all the pixels. For each pixel it iterates through that is greater than the threshold, it will check to see if that pixel is already part of an island. If it is, it will again create the pixel neighborhood, adding each pixel in that neighborhood that is above the threshold to the island. If it isn't part of the island, it will create a new island, and again do the process with the pixel neighborhood. Once all the pixels are iterated through, it will count up all the pixels in each island and display the largest one. 

Writing this all out makes sense, but I am having trouble figuring out how to tell LabVIEW when a pixel has been "marked", or how to add a pixel to an island. I have included my code so far, but please let me know if you have any suggesetions or comments! Thanks so much!

[Katie_Lab4]

Hello all!

I am trying to create a code that will iterate through a 2d array, and create a "marker" that allows the computer to know that cell has been iterated through already. For example, if it was a 4x4 2d array, there would be 16 markers. I am having trouble figuring out how to do this and was hoping someone could help me.

Thank you!

[crossrulz]

You could make another 2D array of booleans.  Just initialize it to all FALSE with the same dimentions as your main array (use Initialize Array) and you can store it in a shift register on your loop.  Use Replace Array Subset to set the marker for the specific index to TRUE when you iterate through it.

But if you are just iterating through with FOR loops, why do you need this marker?

[GerdW]

Hi Katie,

what about a 2D boolean array of the same size?

[Katie_Lab4]

Thank you for the response! I was thinking of using markers because I am trying to make a code that iterates through a 2d array, and for all values that are greater than a certain threshold, I want to find the 8 surrounding cells (pixel neighborhood) and add any cells who's value is also greater than the threshold to that same marker. Then, as it keeps iterating through all the cells, it will check if the current cell is part of a marker already, and if it isn't it will create one. 

I was having trouble figuring out how to create the markers, but I will try your method! Thank you!

[billko]

Interesting.  Sounds almost like you want to roll your own nearest neighbor interpolation.  Sorry I offer no solution, but this is an interesting convo that I want to keep track of.

[Bob_Schor]

Katie,

     I'm sorry that I haven't responded to your post -- despite "staying at home", I've been pretty busy.  I just noticed your response, took a brief look at your code, and said "I wonder how such a data set looks?".

     So I did what LabVIEW encourages, I started "playing" with the problem (LabVIEW is, after all, an "Experimental Workbench", I'm a scientist by training, so I'm "into" Experiments.  Here's what I did -- I built a 40 x 40 Array of N(0,1) (normally-distributed Random Numbers with mean 0 and variance 1) and created a 40 x 40 Boolean Array that is True of the value is over some threshold.  You can, of course, use the Normal Distribution to determine the mean ratio of True to False.

     What I found fascinating was the behavior of "Island-making", where I used your definition of "surrounded on all 8 sides by Black (False) squares".  If I set the threshold at 0, where 50% are expected to be True, the map shows essentially no Islands other than isolated islands of 1-3 squares touching an edge (which would disappear if we made the surface into a toroid).  With a threshold of 0.5, we expect 31% to be True; we still have "edge" islands (more of them than in the 50% case, probably because the world is now 69% "water").  There are a few small "interior" islands, but most of the land has "clumped" into what I estimate (on a 20 x 20 map, looking "by eye") to be about 10-20 weirdly-shaped spindly continents (reminds me of Voting Districts).  A threshold of 0.75 (about 75% water) now has mostly small islands, but with some larger "skinny continents" where you can usually walk no more than 3-4 blocks (including walking diagonally) without having to turn somewhere.

     I suggest you try your hand at making Random Maps (as I've done).  I suggest you use Square LEDs (I made mine 10 x 10, and the World Map 20 x 20), and use a Random Number generator to create Islands.  LabVIEW provides a nice U(0,1) Random Number Generator, which is easily turned into a pretty good approximation of an N(0,1) Generator.  Oops, U(0,1) means "Uniformly Distributed between 0 and 1)", while N(0,1) means "Normally Distributed with Mean 0 and Standard Deviation 1" (a Normal Distribution is also called a Gaussian Distribution).  To make the Approximate N(0,1) generator, take the sum of 12 U(0,1) numbers and subtract 6 (the expected Mean) -- the result will be very close to N(0,1)!  [These days, I suspect most students don't learn this ...].

Bob Schor

[Katie_Lab4]

Hi Bob! 

No worries for your late reply, but thanks for not forgetting about me! I like your method of creating "islands" using LabVIEW's random number generator, but what I'm really trying to do is then figure out the size of those islands. In other words, how many cells or elements of the 2d array comprise one "island". Once I have the size of all the islands, I could then determine how big the biggest island was. 

While using a random number generator is helpful to visualize the input data, my data won't be so "random". The purpose of this code is to try to identify discrepancies in a data set. I am basically taking the intensity values from a heatmap, and trying to figure out if there are any "islands" of intensity values over a certain threshold and how big the biggest island is. Ideally, there should really be no islands, but I am trying to detect and instances where there are. 

I know this problem is kind of hard to conceptualize, and I apologize for how confusing it is. I am also having a hard time conceptualizing it, and I came up with the problem. I am definitely still a beginner at LabVIEW, so I am hoping the community of more experienced members like yourself can help me (as you have been doing thus far, thank you!).