koobas.hobune.stream
Order points from array based on 8-connectivity (Moore neighborhood)
Well, I'm working with pixels right now in Unity... I was wondering if anyone could help me with this.
For example, I created an image like this:
https://i.gyazo.com/4beb60124cab41d31500968c6b4833e1.png
And now I store every black pixel in a List<Point> like this:
//Think that I can get all pixels as an Color[,] array (actually, I can)
List<Point> points = new List<Point>();
for(int i = 0; i < width; ++i)
for(int j = 0; j < height; ++j)
if(colorMap[i, j] == Color.black)
points.Add(new Point(i, j));
Now I have stored all the points in a List, but with the problem that they are ordered as the image was looped out. So, now I have the question, how can I order it?
I have tried something like that:
public Shape SortDistance()
{
List<Point> vlist = vertices.ToList(), //Get all the vertices in a list
orderedList = new List<Point>(); //This will be the final list
Point fp = vlist.Find(x => x == position), //Get the first pixel that was detected before... (This is )
curPos = fp;
int maxLoops = vertices.Length * 10, //I tried to avoid freezes without luck
lp = 0;
while(vlist.Count > 0 && lp < maxLoops)
{
var clockwiseDirs = new Point[] { Point.upperLeft, Point.up, Point.upperRight, Point.right, Point.downRight, Point.down, Point.downLeft, Point.left }; //8-connectivity array
List<Point>[] neighs = new [] { new List<Point>(), new List<Point>() }; //This is a little bit confusimg, but here, the only trhing I do, is store in the first array the 4-connectivity (up, left, bottom and right) points and in the seconds the corners
foreach (Point p in clockwiseDirs)
{
int j = p.x,
k = p.y;
if (j != 0 && k != 0)
{ //If this position isn't the center...
Point nPoint = vertices.FirstOrDefault(x => x == curPos + new Point(j, k)); //Check if there is any pixel, if not return null
if (nPoint == null || nPoint == Point.zero)
continue; //And skip...
List<Point> mergedNeighs = neighs[0].Union(neighs[1]).ToList(); //If yes, merge the two arrays
if (!mergedNeighs.Contains(nPoint)) //Only for check if this points wasn't already added
if ((nPoint - curPos).sqrMagnitude == 1)
neighs[0].Add(nPoint); //If the distance is 1 it means that the position is top or left or bottom or right...
else if ((nPoint - curPos).sqrMagnitude == 2)
neighs[1].Add(nPoint); //If it's 2, it means the corners
}
}
bool n1 = neighs[0].Count > 0, //Sides
n2 = neighs[1].Count > 0; //Corners
if (n1 || n2)
{ //If it has neighbors
List<Point> mergedNeighs = n1 && n2 ? neighs[0].Union(neighs[1]).ToList() : neighs[n1 && !n2 ? 0 : 1]; //There we have to sleect what we want, depending on the neighbors found before
foreach (Point ne in mergedNeighs) //Now we loop over them
{ //Comprobamos cada uno de los vecinos
List<Point> fPoints = new List<Point>();
if (!orderedList.Contains(ne)) //Check if the final list doesn't has this point
fPoints.Add(ne);
if (fPoints.Count == 1)
{ //If there is only one neighbor
orderedList.Add(fPoints[0]); //Add it to the fional list
vlist.Remove(curPos); //Delete it from the other list
curPos = fPoints[0]; //And set the new pos to revise
}
else
{ //If there are several neighbors
Point np = fPoints.FirstOrDefault(x => x.sqrMagnitude == 1); //We select the nearest one
foreach(Point vp in fPoints)
orderedList.Add(vp); //They are orderer, so we have to add them
vlist.Remove(curPos);
curPos = np;
}
}
}
else //If the pixel is alone remove it, impossible case??
vlist.Remove(curPos);
++lp;
}
if (lp > vertices.Length * 5)
Debug.Log("Mmmm..."); //If this goes up something is going wrong, but I have noticed it because my pc freezes
vertices = orderedList.ToArray();
return this;
}
I'm aware this is better to be in Code Review, but I don't know, I have to optimize it, but first fix it, because I think that the while freezes, but I have small RAM size and a lot of "Shapes" to check, so I cannot know exactly where it fails, because, my PC freezes.
One option could be to make a coroutine, but my problem there is that my script is a messm and If I do this I could cause a null object reference.
If anyone could help me I would be so happy! Thanks in advance.
I'm not quite clear on HOW you are deter$$anonymous$$ing the sort order: but rather than perform the sort yourself, I recommend you use List(T).Sort https://msdn.microsoft.com/en-us/library/w56d4y5z(v=vs.110).aspx
Create a single comparison function, between two points, that will define how points should be ordered. Pass this function to your list's Sort function, as in the example in the link above.
But, from your code, it looks like you might be doing a bit more than simply Sorting the list: is that correct?
Actually, I use Sort to order them according to their position to the center and their angle within it. But, in very enclosed points the algorithm fails, and it order following their angle not their real position... So I was wondering If it was possible to achieve what I need by using 8-connectivity.
Your shape is a concave shape so using the angle to some sort of center point won't work. That only works for convex shapes.
Your problem can be solved easier when you work directly on the grid. Do you really need all pixels or is it enough to get the boundary pixels? Because keeping those extra pixels just creates ambiguity where the path continues.
So there are two solutions depending on if you want all pixels or the boundary pixels:
Getting the boundary pixels is the easiest and most straight forward. You simply pick a point that is for sure on the outer boundary. If you simply scan the image row by row the first pixel you find does met that criteria.
Now you simply go ahead in the same direction on the x axis. You know that in the row below the current is empty since in the current row you found the first pixel. So the pixel you've found is one of the lowest one on the y axis. (just in case you didn't know, images are stored left to right and bottem to top. So the first pixel is the bottom left pixel in an image).
For this algorithm you have to store / carry over to the next step:
the current position
the current direction.
The direction can be an enum / int with 8 values or a direction vector. The logic is now this:
Check the pixel that is 90° clockwise from the current direction.
If there is a pixel, store it and set the new direction to this direction
if there is no pixel rotate the direction 45° counter clockwise until you find a pixel
repeat
Note that if the shape is a closed shape you should end at the starting pixel. Though it's possible in some cases that you get stuck somewhere. If might be a good idea to build in some safe-guards. Either remember which pixels you already processed and terminate when you reach the same pixel again, or simply restrict the amount of iterations. (you never need more iterations than there are pixels in the image ^^).
The resulting list is already sorted since you walked the boundary in counter clockwise order.
If you want to process those extra pixels as well it get's a bit more complicated. You can use the same procedure as above, but in addition each step you would also check the "next" 45° rotation and if there's a pixel you add it in between the current and the last.
So it's basically like this:
Check the pixel that is 90° clockwise from the current direction.
If there is a pixel, check 45° counter clockwise and if there is another pixel add this first. Now add the current pixel
if there is no pixel rotate the direction 45° counter clockwise.
repeat
Note that this will also only process a "connected" path. If there are additional pixels inside the path that aren't part of the outer path, they will be ignored.
If you plan to have multiply pathes in one image it can get tricky. The easiest solution is as you process the pixels you actually remove them from the image data. So once one path is done you can simply continue the search for the first pixel from the last starting position. A safe way to remove a completed path would be to iterate through the path and remove the 9 pixel area around each path point. This ensures everything that belongs to this path is gone.
I haven't tested this approach but it should work as described. The "rotation" can be easily done with adding / subtracting from the int / enum and wrap the value properly, or when using a direction vector by some simply vector math. Rotating a 2d vector by 90° you simply flip x and y and invert one of them. Depending which one you invert it's +90° or -90°. 45° can be easily done by adding the current vector and the 90° rotated version together and "normalize" the vector. "normalize" here means ensure each component is either -1, 0 or 1. So a 45° vector would be (1, 1) so it can be used as offset into the image grid.
edit
In case you don't know what boundary pixels i mean, see this image:
Thanks for your long answer! Well, I did this as you stated, but for some reason it failed (it gets less shapes than the number I wanted *), and I prefer using another algorithm that is called CCL (Connected component Labelling), but now I've realized that I can use this to process several shapes at the same time.
(*) I have an image that's 7000x5000 with 2877 shapes, I believe that only 2300 were detected incorrectly, but I can now process the 2877 shapes in less time.
I'm very busy this week, so I only could to do something right now... And well, this is my unlucky result:
http://pastebin.com/a$$anonymous$$Ut6ZXD
I actually did what you said... But, nothing works, I have to debug to know where it fails. As I know, it doesn't not detect any point by the moment.
@Ikillnukes:
I haven't tested your code, but your GetDir method has several "bugs".
private static Direction GetDir(Direction dir, int n)
{
if (n == 0) return dir;
return (int)dir + n < dirLength ? (n >= 0 ? dir : (Direction)dirLength + n) : dir + n - dirLength;
}
I guess this method should actually "rotate" a direction, right? Let's have a look at some cases.
The usual case is that "dir + n" is still in the valid range so we just should return this. However in none of your cases you return "dir + n", even that's the most likely case.
If n >= 0 you always just return "dir". I guess you wanted to return dir+n
if n <0 you don't use dir at all but return the "-n th" element from the back. This makes no sense ^^.
You don't check the lower bounds at all.
It's by far easier to simply offset the current value and then rotate it around:
private static Direction GetDir(Direction dir, int n)
{
int v = (int)dir + n;
if (v < 0)
v += dirLength;
else if (v >= dirLength)
v -=dirLength;
return (Direction)v;
}
Personally i wouldn't use an enum but simply a vector / point but that shouldn't matter.
Can you, by any chance, share your image? Or is it a secret? It would simplify testing my own code and we could see if there are any problems with some shapes. I haven't mentioned it explicitly but of course it only detects the "outer bounds" of a shape. So for example and "8" shape would come out as something like a "0" as the middle line is never traversed (with the exception of an "8" with 1 or 2 pixels in the center).
I just implemented what i explained in my answer myself. Here's my solution.
I used my own "Vector2i" struct which was easier to use in my case. Note that the "drawing" code in OnRenderObject is not very optimised. It simply draws a line from point to point and "closes" the line loop by drawing a line from start to end.
I used this image as source. The result is this.
Note that i have placed all problematic shapes at the bottom. Here are the reasons for the wrongly detected shapes from left to right:
The top of the star consists of a single line. So it can't find any pixel to continue except the one it came from so it finishes the shape. That's why the top left part of the start is a seperate shape.
The second star has the same problem. The right tip of the star is also only one line thick. So it breaks here. Note that the remaining shape is now iterated on the "inside" since we start with the bottom right pixel. That's why there is a tiny fragment at the top left as seperate shape.
The two inverse U shapes are included to show that the big outer "U" is traversed from the bottom right on the "outside" of the shape, while the small inner "U" is traversed on the inside. So the outer shape is ordered counter clockwise and the inner shape is ordered clockwise. Shapes should always be "closed" so they are detected correctly.
The 4th shape is just a single line so it's not a closed shape.
The next two "U" shapes are identical but the top one is closed. As you can see the bottom shape is splitted into two shapes. Since we start at the bottom left the blue / cyan shape is found first. When the algorithm reaches the top right it stops.
The last shape is that cloudy speach bubble thing from $$anonymous$$S paint. Since it's closed the boundary is traversed correctly. Though since the shapes has some pixels going inside those are detected later after the boundary shape as been removed.
I've played around a bit and created a WebGL live demo(located on free hoster). It allows you to view the parsed shapes as line loops interactively. You can zoom (scroll wheel or right mouse button) and pan the view around (left mouse button). It also views the source texture in the background.
I added a "rendering animation". It will always highlight a single line segment of each shape in "white" which will traverse through all segments over time. This helps to see which order they actually have been detected. I also show some stats like: how many shapes it has detected, how many points / pixels all those shapes have in total and how long it took (on your PC, in web javascript ^^) to parse the source image. On my PC it took about 240ms in the WebGL build. Strangely when i run it inside the editor it takes 1100ms ^^.
Sometimes my browser (FireFox) said that the webGL application run out of memory, however the last few times i tested it just works as intended.
So i think that's enough for a "prove of concept" :) I also modified the actual detection code and inlined most methods which greatly improved the speed. If you want to see the latest version that the WebGL build uses, just have a look here. The two materials have to be supplied to the script. Line$$anonymous$$at just uses the "Particles / Alpha Blended Premultiply" shader and the "tex$$anonymous$$at" uses "Particles / Alpha Blended" with the texture assign and a small alpha value as tint color.
The scene uses an orthographic camera which is located at (0,0,-10). The script is attached to an empty gameobject at (0,0,0).
