DIP Lecture 11: Edge linking and line detection

okay so last time we talked about edge detection right so purely the question of how do we find pixels in the image that correspond to edges and those could have been like you know we could have designed generalized detectors like the laplacian that respond to whatever edges there are an image or we could have used detectors like so bullet vectors which are sensitive either horizontal or vertical edges we could even use bigger edge of ASPs to help us detect edges in diagonal directions for example but I'll talk about today is a little bit more like how do we put these edges that we've detected together into more useful constructs right so at the very end of the last lecture we talked about the canny edge detector which had this nice property that it seemed to do a pretty good job of outlining you know objects if we tuned those high and low thresholds corrected right so kind of one question is how do we use those you know close curves that we can see in the image how do we describe those mathematically so it's got in the first part and the second part is sometimes we want to do something very specific for example you know suppose I want to detect you know doorways and windows in an environment one opportunity or one idea would be to search for long straight lines those are the kinds of things that make up man-made objects in the world and so we want to talk specifically about how do we take this massive edge missiles and decide which ones they lie on straight lines in the world okay so first kind of thing I talked about is edge linking okay so it is that we've got a edge map and we'll say we start with edge pixels and corresponding maps for the magnitude of the edge response and the angle of the edge response right and so one idea that we could have is why don't we try to connect up edges that have similar orientations right and I won't only want to do that edges that have sufficiently large magnitudes and so the idea is for each pixel for each edge pixel XY so now for now we're only going to consider kind of a binary map of pixels that made it into the edge map right so things that have passed our Sobel detectors are applause again and now we basically have just either pixels at an edge or a pixel it's not in the niche okay but those that Matt's are still typically pretty noisy so it is for every edge pixel we make a window so let's call that s XY around that pixel right so kind of the zoom in is that here's my image you know here is my edge Mixel and maybe here is my window and then what I do is to say okay for each other pixel inside that window link the center pixel to that pixel if for example the magnitude of the edge is similar so that's less than some threshold and the angle of that edge is similar rights idea is to say okay you know say that this estimated estimated angle is that the edge is in this direction okay and so that may correspond to some sort of a actual edge passing through the image so maybe what I say is okay you know I don't care about what's going on at my neighbor over here I want to look in the direction of where my edges pointing I want to have similar orientations and I only want to connect up local edges if the magnitudes are similar right so I don't want to connect up weak edges that happen to have the same angle I only want to do that for kind of strong man to edges and that way you can do things like maybe you can bridge gaps that you missed before you can kind of build edges into long strings of pixels okay so this is gonna be used to kind of trace out long edges because what you're doing is just kind of following your nose along the edge direction and you stop doing that when the magnitudes are not so large right so that's one way to kind of make you know long strings of edges once you've got these long strings of edges the next thing you want to do is kind of try to describe those right and so remember last time we had this issue where we had basically like the window of a building or a door that was pretty well out and so the next step I want to think about is how do we follow that boundary around and describe that boundary and then we can say okay now I've got this window that is encoded by this list of ordered pixels around the edge so I would say the next step is kind of boundary following and this is like saying you know we have edge points around a closed contour or I guess it could be an open counter but let's talk about closed contour and we want to you know kind of link or order them and let's say in a clockwise direction and so what I'm going to tell you now is an algorithm called Moore's boundary following algorithm okay and what that's going to do is it's going to take a set of edge pixels and so I've already prepared a little map of edges right so suppose that this is the you know set of edges that I've gotten around some close contour and I want to assign a natural order to these guys right in such a way that then maybe I can compare the orders that correspond different objects and do things like object matching right so say it's the thing that describes my ethic I want to find similar things on the conveyor belt by matching up the boundaries right so let me describe to the algorithm first thing we're going to apply it to this little blobby image so I'm going to write down the algorithm on paper first and we'll come back to actually doing it so the algorithm is as follows so first get to decide on place to start so we're going to let the starting point which we're going to call B 0 be the uppermost leftmost point labeled one and so by label one I mean kind of the initial position is that we have an edge map you know one equals edge pixel zero equals not okay so we start with a binary image I'm gonna find myself the first point basically I'm saying I'm going to take the point in the top row that is to the leftmost right so here's my top row this guy would be my B 0 okay and then I'm going to let C 0 be the left neighbor of B 0 and so here in my map here c0 is going to be this guy and I know that this can't be an edge point because by definition I said that b0 was the leftmost edge point in the top row right so this couldn't possibly be an edge point okay and now I'm going to do is I'm going to start looking around my neighbors starting from c0 and look lockwise for the next edge point okay so the next step is examine the eight neighbors of b0 starting at C zero and going clockwise and I'm going to let b1 be the first edge point that I find and c1b the preceding zero right so in this case what I'm gonna do is I'm gonna say okay so I'm going to say well I'm gonna start with this guy I'm going to kind of start searching my way around and the first new guy I'm gonna find is here right so kind of I started here I went all the way around and I found this was my next edge point and then I'm gonna let c1 be the preceding blank space right again that can't be an edge because I found the first - right and then the idea is that now I basically start over again with this B and this C so kind of I'm gonna say you know I let you know B equals b1 and C will see one and then I keep on repeating this process of updating B and C so let me go around for a while so okay I'm gonna say now I'm gonna start here I'm gonna go clockwise from this point until I get to my next point here this is C 2 then I'm gonna go like this this is my P 3 this is my C 3 now I have to go all the way around here to find B 4 this is my C 4 and so on alright so I'm just gonna go kind of follow my guy around here pretty mechanical so you might think that there's nothing really hard about this algorithm and you would be right the only thing I can think about is what happens around these bolts here's we're gonna talk with that just a second so I'm following following following following clockwise to this here I'm gonna follow lockwise here we'll just be 13 c-13 okay and then I'm almost about to stop right so when do I stop I'm gonna say my stopping criterion over here I'm gonna stop I'm gonna continue until I arrive back at my starting point and the next boundary point found is b1 in this case we don't really have this problem because if I start here at your seat well if I was trying to be 13 so I label this right I think this is this is super right right it's these relative that I follow us around and I ride back here and this is my kind of B you know this would be what I would call B 14 but then as I find this around I find that I would have gotten back to the same point it may not seem like I need to have this little caveat but the reason that I need it is in cases where you know this b0 is kind of tucked in a weird way around you it's kind of hard to explain what the coroner cases but suffice to say that you need it right so basically I just keep on following the edges around now you can see I've got this kind of nicely ordered list of edges and then that's it so basically the ordered list of B's is the doctrine right and so this basically once we describe the boundary and now I think about how do I actually take that information and keep it in some sort of concise way one thing that I could do is I could use what's called a chain code to represent the order of the boundary pixels so once we have such a boundary we can describe it with for example let's call the chain code and the idea is that what I do is I define three bit Direction corresponding to the direction of my next boundary point and for convenience in those start zero over here and so what I could say in this case is okay I've got my boundary in terrific build up of the same thing but I can basically say what direction does my edge point to in each in each case right so in this case you know going from B 0 to B 1 I go into zero direction to go from B 1 to B 2 I again go into zero direction and let's see if I can kind of get this all on one screen to go from v2 to b3 I go in the zero direction to go from here to here I'll go in the southwest direction which turns out to be 5 here are the South which is 6 South again South again 6 6 then I go east west for 3 steps for 4 then I go north for one step which is 2 I go Northwest northeast and I know I'd be lost in the forest apparently if I do this then I go this way then I go that way and then I'm done right so this is like a very concise way of describing things and of course this order kind of depends on the starting point right so the order dependence on the starting point which you know by convention we said was the upper left-hand point but you know suppose that we wanted to compare two shapes one that was like this and one that was like this on its side right those are fundamentally the same shape if I started to describe them with the chain code I've got two different chain codes one reason is that you know the upper left-hand point would be different and the other reason would be that the order of directions is going to be like 90 degrees reversed from this guy right and so we can sell that with two issues one is that for example we could so to be able to match shapes of different orientations we can one for example order the chain code so it always starts with the minimum magnitude integer by that I mean you know here if I look at the possibilities right here re you have start with zero that would be good but the other thing would be if I had chain code where zero is somewhere in the middle I could just cyclically shift this whole thing because you know this thing kind of defines the same shape no matter where I started sequence and so what I can do is just shift this around until I start with the lowest number I have right so that's one way to kind of make things you know invariant and the other thing that I can do is just encode the difference between directions right and what I mean by that is that here this chain code is kind of giving me an absolute direction right go east go east go north right the other thing that I could do is basically say actually instead I'm just going to tell you how many clicks around the eight-sided clock you have to go to get to the next edge pixel right so for example I could turn this guy here into a difference one where I say okay there's no difference between me and this guy so I'd say that's difference of zero there's no difference between me and this guy that's difference of zero there's difference of five clicks between missed me in disguise that's five there's difference of one click here then I go in the same direction the same direction the difference between four and six is like going like six clicks in the wrong direction so we're talking about mod eight arithmetic that's not saying to get from four to six I have to go six around right so to get from zero to five I had to go one two three four five yeah yeah I guess then here I couldn't go any counterclockwise right so I'm saying that here the difference is five to zero so I'm kind of talking about how many clicks counterclockwise have to do so to get from four to six I have to go one two three four five six right so then I go that then I have to again not do anything then I have a to get from four to two I have to go again that's like a six guy then I have a seven then I have a two then I have another seven and then to get back to the starting point I have a sudden right so these are like the differences and the advantage of this is that then even if I had this shape and it was rotated by like 45 degrees my chain code with the differences would still be the same chain code no matter which way I turned this as long as I was in a 45 degree clip right so that would be like a very nice invariant way of describing the shape and so one of the pork assignments is basically to code up this little algorithm and so I can show you my implementation of it so let's see here I guess I need to get to my desktop sorry about this yeah so of course Matt light has some built-in stuff for you do this but I would like to see you try and do it yourself so we're doing here okay so here I have a little shape that I made actually think this is maybe the same shape that's on the homework so again this could be the result of doing edge detection and a little tiny guy see you let me get little here alright so here's my binary edge now right and so I want to just follow that around and I just wrote a little function to do that that I called edge link they move over here stay there okay hopefully it'll work so kind of here you see I'm sorry so small is that I'm basically just the red point is my current edge point the blue point is my previous edge point you know you can see it kind of went by fast I can just kind of show you again that there's one little blip on this guy where there's actually kind of an interior edge point and we shouldn't count that on our list of edges right so one nice thing about this boundary tracing algorithm is it ignores any edge pixels or white pixels that are fully inside the shape so I don't want to really count this guy and you'll notice that as it goes around it doesn't actually count that interior point so I don't know if I can make this bigger where that will complain alright so you can see you kinda just ignored that little point in the middle there and as it's going around it's checking different things this is so many ways I was checking it's just like investigating all the neighbors starting from the good thing it's also keeping track of what direction did I have to go to find out where I was at the end of the day when it gets back up to the upper left-hand corner it will spit out for me basically a list of pixels and if I had been smart enough to ask I would have also gotten the chain code so I guess I can just show you so this is what I'm gonna ask you to code up yourself I guess we have to watch it play again and of course while we're doing this I guess maybe I can't do this while MATLAB is moving there's also a MATLAB command called BW trace boundary which I probably shouldn't tell you about anyway so this is kind of like the MATLAB function that will give you some boundary pixels now you know just I'm not sure that that labs function corresponds exactly to the algorithm I just told you I think it's probably pretty similar but you know you can try to try to check your work against this if I'm not entirely sure that gives you exactly the same output in the way I just defined it FYI and let's just see where we got and so yeah here you can see that the second output that I asked for was this chain code so here I find out that I have 81 pixels and this tells me the direction I had to go to get to each pixel right I didn't do the differential chain code anything here but we pretty easy to do to convert them okay when you're doing the modding how do you know the market right so here basically to be really clear I'm taking you know this guy - this guy mod eight right so it's now I'm saying I take VI plus 1 minus bi ma date right and so when I have a positive difference then I should have a you know number basically less than four right so 6 minus 5 is 1 here when I look at 4 minus 6 mod 8 I have minus 2 mod 8 which is equal to 6 right so I think that's the sanity check as if I'm you know if if I'm greater than my previous neighbor I should be kind of in the 0 to 4 clicks this way if I'm less than my previous neighbor I'm going to have between you know 567 I guess four five six seven right so yeah yes I keep track of you know and of course this would be very easy to do in MATLAB right if I looked at my output which is somewhere right so if I looked at my output I could do something like just look at the let's just say I just look at the first 20 of these guys so I could just say for example tell me what this from the second to the end - these guys and then I could just look at this whole thing body right it's like that would give me all I would need right so there's no need to actually manually worry about doing okay so other questions or comments about this kind of edge linking algorithm okay so this is all still pretty kind of crude like pixel level instead of what I want to focus on for the rest of the time is a little bit more like do you know geometry good level description of what might be going on right so a natural thing that I might want to do is to take a set of pixels and turn them into edges right so if I look back at my shape here one thing I might want to try to do is to describe this shape as a polygon right so I want to for example turn this in something where the top is a straight line and this is a diagonal and this is another straight line this is a straight line right so how would I kind of find the best polygon that would succinctly describe the shape right obviously I could use the pixels themselves as a very kind of fine detail shape but I mean that would be kind of overkill right in the sense that you know here I don't want to have to kind of approximate this thing by a series of tiny polygonal segments I want to take this whole swath of points and describe it by a nice straight line that roughly passes through the points right so basically you can imagine that I could devise a polygon filling algorithm that would have as one of its parameters the tolerance for how carefully I wanted to fit through the edge points as long as my tolerance was not basically you know zero tolerance for error then I could get away with describing this thing as a nice polygon so let me tell you about one such algorithm for polygamy fitting so loganville fitting to a set of ordered points right so kind of you know we imagined that we have as a prerequisite I've already followed my edges around to create an ordered list right so that was kind of this boundary following algorithm is a prerequisite before the algorithm gonna tell you about next and so the idea is something like this you know suppose that I have some you know set of edge points which I'm just using in circles but don't lie exactly on straight lines kind of what I want to be able to do is to turn this into a reasonable polygon I'll consider that to be a success as long as none of these points is kind of sufficiently far away from one of the lines right I mean as I was saying earlier it will be overkill to connect the dots right connecting the dots would yes give me a polygon but it wouldn't be a very useful one because it would be just so fine detail right again this is a good thing to do for example if I want to try to find you know roughly fine rectangles and roughly fine triangles in image I maybe want to connect up these points right so now I'm going to tell you about an algorithm that does that okay and the rough idea is pretty simple so I'm going to give you a rough rough idea at first then we'll talk about a little more detail so let's let P be a sequence of ordered distinct points meaning no repeats right and so for example this in our case corresponds to ordered edges after a boundary column okay and so now I'm going to do is I'm going to specify two kind of starting points a and B okay and this pair of points is slide that we're depending on whether the curve that I want to fit is like a closed curve luck going around the window or whether it's a straight line or not certainly whether it's a open it a curve like maybe following the boundary of an arch we're not done so I don't have necessarily have a closed curve but if the curve is open then basically a and B are the natural end points if the curb is closed I would choose for example a and B to be the left and right most points okay and then I also have to specify a threshold which I'm going to say is T and T basically says you know that's how close every point is ultimately going to have to be to one of these boundary lines okay and now I'm going to do is kind of like this question yes so this is the pixel distance so T is measured in pixels and now we're going to do is I'm going to make two steps of points that are kind of going to tell me the order I'm processing these vertices okay so basically create two stats this is kind of a computer science II kind of way of the game of this one I'm going to call final and one I'm going to call in process and I'm going to initialize the final one as being one of the endpoints and the in process one is going to be BA and I'm going to assume that I'm using a closed curve just for this example if it's open curve you would use just a and now what I'm going to do is execute the following steps and so I'm going to write this down kind of mechanically on pieces they reversed I'm going to show you an example with a pair of with some actual points so the first I'm going to do is I'm going to connect or I'm going to compute the line connecting the last vertices of final and in process okay like a second actually just jump to a picture here so here's a picture of a set of points where I want to fit a polygon - okay and so I've done what I said I have initialized a and B as being left the rightmost points in this collection of edge points okay so the first step that I just said was computer line that connects the last vertices of the two steps and so the two stacks are B and BA so I want to make a line between B in it okay that's pretty easy to do so here's my line okay now I'm going to compute the distances from this line to all the points between these vertices okay so I'm going to compute the distances from this line two all points between these vertices and so here between is going to be in the in the sense of kind of going between them in a so if I said be to a in a counterclockwise direction okay and I'm going to select the vertex or the point the mass with the maximum distance D max okay so let's look at my picture so here if I'm going from B to a and I'm asking okay well what is the vertex that has long assistance this case I'm just looking at straight line distances like this and so clearly this guy here is furthest away from the line right this is going to be my maximum vertex and so let me make that you know I'm gonna give that guy a new name see okay this is the worst guy very bad and so now I'm going to say if this distance is bigger than the threshold that I set then I'm going to put this new vertex that I named at the end of in process and go to step 1 okay so now what I do is I say okay let's keep track of what my stats are so here I'm gonna make final on this side and in process on this side right so I started with the stats being B and BA right I found these points I found this is my worst offender and then I said okay well in this case I need to add a new point to the end of in process okay and I go to step 1 okay alright now I go back to step one I say now I have to connect these two vertices right and what is my worst offender right so again I'm gonna connect this line here and let's suppose that my T is you know like yay big okay so not very scientific but basically in this case I can see that hey you know neither of these points in in between B and C are particularly bad right they are a pretty good polygamy so let's see what happens when I don't violate the constraint because ERISA okay this is my worst case scenario but it's not really that bad okay so let me see what the next step of this algorithm is the next step is saying you know otherwise remove the last vertex from in process and make it the last vertex of final okay so that means I'm gonna take this guy say okay see you guys are good I'm gonna move you over to final okay now what I do next well I'm gonna start again but let me just say that if my in process is not empty go to step one if it is empty done and the vertices in my final list are the ordered vertices of the polygon okay so let's see what I would do here so now I would say okay now I'm gonna connect from A to C again I'm pretty happy that neither of these guys is particularly bad right so now I'm going to say okay that means I move this guy over here now I have to connect from B to a okay that's the same line but now I'm going the other way right it's not if you look at my worst offenders in this direction and I would come up and say hey you guy are pretty bad right he is pretty bad so now I have to add this new vertex over to D now I'd connect D to a and I say ok you are okay so I think I can successfully take D over here and then I connect B to D I gotta say you you are okay too then I move B to here and now I've got this word vertex list BC ad B that gives me a pretty good polygons in right so that's pretty easy and you know that's a very simple way of fitting a polygon through a set of points and obviously if I wanted a you know more strict fitting polygon then I would turn my threshold T down and in fact if I turn that T down to like you know putting 0 0 1 then I just end up basically connecting the dots into a more jerky polygon right now obviously those of you that know like computer graphics and so on will probably also know other methods for connecting lines into smooth curves right so for example you've probably heard of like cubic B splines right so those of you that are computer graphics people have promised that splines through families of points and that's a possibility too so I mean there are ways of for example fitting a nice you know spline II boundary around here and those are a little more complicated I don't talk about them right now but they're also kinda straightforward extension that's right you know you could argue about whether it's easier to represent things with polygons or splines right so in the early days of video games all of the objects were kind of political platform services are more like spline services right so a lot depends on what you're what you're doing it for okay so questions or comments about that I'm not gonna ask you to actually yes right so yeah what happens when you've got an outline that is beautiful but one point is missing like a gap okay so that's a good question so I could have certainly something like you know suppose that I had like this was my set of edge points right so how do ya so in this case when I would follow this boundary around I would it's actually the the algorithm I told you about is really looking at closed curves right so for one thing the algorithm would probably like go around the exterior of the curve and they kind of go around the entry or the curve and come back right so you kind of get this double list what I really want to do is I want to bridge this gap right and that's actually going to be the topic of today we're going to talk about next week which is called morphological image cross right so when I've got these binary images it's very common that there are either gaps like this or there are extra blobs that I want to get rid of and so it's definitely possible that I want to do some pre-processing on my edge before I start to do this higher-level reason so I want to connect up that gap before I apply the algorithm so let's talk about that gap feeling actually for sure good question well then you go the Tricky's the question is would you want to look at your you know like 5x5 set of neighbors right and then potentially jump over the gap honestly I don't know that that's very common right so typically you only want to deal with pixels that are really connected to you right because then you run the risk of you know suppose I had some other crap pixel over here that wasn't connected at all then I would jump over there and then everything would go to home it so yeah so usually you don't want to make too many inferences at all it might be happening too far away yeah other questions are coming okay so the last part of lecture I want to talk about a very particular problem which is fitting straight lines and images okay so you know when you've just got one straight line in an image right so suppose that I had you know suppose I have just like beautiful straight line maybe it wasn't exactly well now let's I guess I should yeah suppose I've got like the straight line here and I could apply my algorithm and life is good right but you know what if I have other straight lines in the image like how would I kind of simultaneously find all these lines at once right that's what I want to talk about Nexus because obviously in lots of man-made images you've got lots of lines right it's a like there's just this one beautiful line your image you've got four lines around every doorway you've got four lines around every window and so how do you find those kinds of lines in the image so let's say this is easy to do with the previous algorithm when there's only one line so what about multiple lives and not only that and but I would say it's clutter meaning many edge pixels not on any line so since that's what I want to do is I want to separate the limey stuff from the non lining stuff okay and that's definitely very common in real world images so what I got here so let's suppose that I look at all right so here is a here's an image there are definitely some very strong straight lines in it right and this is actually by the way this is a real image that owner of a space that would look that you might think it was like a good here graphics rendering it was very kind of cool to imagine that there were all these kind of very smooth shapes and so if I were to look at the edges of this image without any you know particular care about the parameters you know I'm gonna get yes lots of the pixels along the edges and again this is just a rendering problem if I were to zoom in on you know here you can see the edges are you know pretty many pixels on these strong edges so I have a pretty good chance of trying to connect those into lines but there's also the distracting stuff that don't belong on anyone right and so I don't want to get myself distracted by all this other possible crap right and so how do I choose which edges why outlines and which ones don't so I'll tell you so it's a pretty clever idea it's called the Hough transform so the ideas is as follows right so let's suppose I have an image and I consider one edge pixel in this image okay now let's think about all the lines that possibly might go through that pixel right it's this line is this line there's this line right there's this in the aligns of every degree going around the circle right so each of these lines so each possible line through an edge pixel can be represented as an equation right so when you were in you know I don't know what seventh grade you learned about representing lines like MX plus B where m is the slope and b was intersection right so that's all that's true although we run into problems like when you know when I've got a straight up-and-down line then the slope is in theory infinite right so I don't want that a better behaved way reading the lines is as follows X cosine theta plus y sine theta equals Rho so in this case theta is like the angle of the line so let me draw a little picture here so again if this is my kind of image space where X is increasing this way Y is increasing that way so here if this is some line theta is like this angle so it tells me the orientation line and Rho is like this distance and so that means that theta equals zero is going to be a horizontal line right that means that a is equal zero I have a line like this and then vehicles there I plug that in is just basically saying that x times cosine 0 is 1 is a constant right and Y is not even equation and conversely if I have theta equals PI over 2 then I have a vertical line and you know row tells me basically how far away is that line from the center of the image so if Rho is equal to 0 this line is going through the middle of the image if Rose I equals 0 the lines further and further away right so instead of using M and B drippers in a line I can use theta and Rho and the nice thing is in this case I have any problems with for example theta is always between you know minus PI and PI and Rho is between you know zero and you know whatever the biggest pixel of the image is right so have any sort of numerical problems okay and so the idea is that you know in the beginning let's say specs will have no idea what other points on it may belong to to align right so what I can do is I can make a list of possible theta and row for every possible line going through that pixel right so a single point in the XY plane here an edge point generates a whole bunch of possibilities theta Rho pairs for locks right so a single edge point X comma Y could belong to many possible lines in the kind of row comma theta world right so what I have is kind of a map that says okay between theta going from minus PI over 2 to PI over 2 I guess and then I have basically minimum values for what Rho could be so this single point here if I enumerate all the possible corresponding lines is that trace out as it turns out a curve it actually looks like a piece of a cosine okay so this here are basically you know possible lines corresponding to some point x1y1 let's say okay and now let's look at some other it okay so now let's pose did I say okay well here this was x1 kind of wildin let's suppose I look at this guy here x2 comma y2 again this guy has an infinite number of lines going through it including one of the ones that happens to go through X 1 Y right so if I take the curve corresponding to X 2 y 2 I'm going to get some different curve and there's going to be a place where those two curves cross over and that corresponds to the line connecting those two points and so the idea of the Hough transform is that for every edge point I generate kind of a quantized version of this space right so what I do is I take the theta comma row space I block it up and do a whole bunch of tiny pixels and for every edge point I basically increment the pixels along this curve by one unit right and as I see more edge points I keep on incrementing those bins and for places where lots of edge points are voting for the same line this guy is going to have a lot of you know people saying hey I'm on that line I could be on that line right and that's the way I were in which lines there are in the image right so it's a pretty clever idea this is kind of like what you'd call like a voting time of algorithm and so let me spell that for you a little more efficiently so the basic idea is first I detect edge points okay so now I have a binary image then I decide on a kind of a subdivision of this Rho theta plane and then for each edge point I increment the corresponding row theta cells in this array by well swamp so I do this for all my edge points right so now I've populated this big array okay and now I look at it and I say I look for Rho theta cells with large pixel counts another way of saying this is I'm going to look for peaks in this array right I'm going to find the places where there are lots of people contributing right and now I'm going to basically you know select the highest peaks and again that's gonna have a user choice about how many of these Peaks I want to keep and then I can kind of map the corresponding row theta into into lines in the XY plane right so every you know every row theta corresponds to some lie on the plane if I wanted to I could even go further and say look for the edge points that voted for that guy and that way instead of getting full lines I could even get like line segments that are actually you know basically or get line segments that correspond to votes okay so let's look at some examples of this right so this is this is a nice real world thing and so MATLAB provides a few functions that help you out with this so the key one is called puff-puff rhyming with tough so basically here this says take a black and white image so basically says take it black and white image that comes out of like an edge detector and it what it returns is the theta in the row so theta in row basically tells you where the how much like quantize each of those things and H is this array that tells me what are the increments each of the bits right and so HUF by itself doesn't necessarily do it all for you right so if I look at this there's a thing that says Huff Peaks which says identify peaks in the Hough transform so I can basically specify I want the ten highest peace in this Huff array and then there's a function called Huff lines that basically says if I give you the edge image and I tell you the row theta a and I tell you the peaks tell me where those lines are in XY plane so you could argue that you could have incorporate this all to one function I did and I called it my huh my huh check it out so here it is so basically this kind of put smell together it says give me an image find me the edges so that's what this BW is and then take the hook transform and show me the hump transformative graph and then I have an argument that says either find me you know up to 50 Pete's according to a threshold that I specified right so I'm kind of saying how high do I want those Peaks to be and then put those Peaks back on the image and so I don't use I guess I didn't use Huff lines I ran my own thing to do that because I think the output of Huff lines can sometimes be able to confusing so let's see some stuff so let's read in some images that have strong lines right so kind of a typical thing right is a Sudoku grid right so there are lots of lines in this image but they're also like every basically letter in this image is going to also respond as an educational right so there's also going to be some clutter and so if I apply my Huff to this image I'm going to get a bunch of stuff right so here's the edge pixel map and you can see that yes I pick up all of the line pixels but also around every number and letter I have edge pixels too right so is it going to act as clutter then here is the picture of the Hough array right so here the x-axis is the angle and the y-axis is the distance the lines away from George right so here what you see is that every one of these light blue curves corresponds to one education and then when I have lots of curves that happen to occur in the same place you get these high-value bins right so here you can see that these yellow and red you know bins are ones were lots of pixels of accumulated right those correspond to these strong edges right and so here those white squares is the Huff Peaks algorithm picking out the places where those guys are maximum and then when I map those guys back on to the image I get these plots right so this is like the best-case scenario one of the reasons is there's nothing else in this image that is like distracting me from finding these lines right if I were to turn down the threshold right so part of the issue is how high do the peaks have to be because certainly there are going to be some coincidental lines right so you could imagine that you know if I were to look at the edges they correspond it to the middle row of this text right there are going to be about you know 40 or 50 edge pixels that are going to coincidentally lie on a straight line right so yeah it's gonna say okay well what is my threshold for how many points are going to be allowed to be contributing to a line clearly I have to have you know 50 or 100 or whatever it is for my given scenario otherwise I'm going to get a lot of line clutter right a lot of coincidental lines and so again this is like the image processing textbook you know example let's look at some more realistic images and see what we can do so I have one called so like I said I showed you the shells one before so let's see how we do on that guy so just as a reminder here is my self image and what do I get if I just were to apply my Hough transform with the default parameters okay so I got a bunch of lines right and actually all these lines are correct because you can see that you know they correspond to different edges of different parts of the shells and if I look in the Hough array so in this case you know there are you know there are parallel lines as there were in the pseudocode example and so here I have different values of theta where the peaks are and you know there are also going to be obviously there are some lines that I missed right so if I if I think about maybe what I would want to do is I would turn down my threshold for the piece to try and pick up the lines that I missed and so what I did in my example was to provide as an extra argument an optional threshold that basically says okay you know find me things that are I think I think this in my function is defined as the fraction of the highest peak so find me things that are from the highest peak to 40% of the highest peak Oh y-you know show uh-oh everything went wrong I think about my syntax the wrong way so here yeah there should be a fraction Oh argh I guess I guess I have to provide a thing like this okay so here if I kind of turn down the threshold I picked up some more peaks than I had before and I also picked up some more edges right so now I've got the top and bottom of many of the shelves no so probably right by the extra edges right so maybe I can be a little bit more generous still and see if I can pick up some more whoa so now things are starting to get a little bit crazy right so here you have to be a little bit careful to actually think about where whether there are some certainly like now I have these diagonal edges right like it's hard to say but like this one where my mouse is right there's definitely no edge in the image that corresponds to that right and that's starting to be edge pixels that are coincidentally lining up to provide just enough evidence for that line right or this vertical edge here obviously doesn't correspond to a real edge in the image so you've got to be careful right so I think that you know again you don't want to accept every line that comes out of this as being a valid line and so there's definitely a lot of post-processing to do on these lines so for example one thing that you could do is you could say okay now I'm going to look at all of the edge pixels that voted for each line and if the edge pixels are not connected together or close together I'm going to throw that line out right so it could be that maybe this vertical line was created by coincidental edge pixels that are scattered along each of the shelves and I say well there's no evidence that there's actually a contiguous set of edge pixels looking for the line so you could do snuggly some post-processing on this stuff let me go back to what my default parameters gave me just to show you know one thing that would be very useful for this so this is actually saying it happens in image processing computer vision is that here there is definitely going to do something that now I can start to reason about the geometry of the camera and the image so for example I could get vanishing lines where all of these you know all of these points all these lines here are eventually get intersect at a point over here all these other lines are going to intersect at a point over here it turns out that those vanishing lines help me learn things about the 3d geometry of the image so I could use this for maybe some sort of like navigation you can imagine if I turn this around I was looking at buildings in Manhattan I think it vanishing lines that would give me some sense of where my camera was in the space that's embedded in some things that are like in Google Maps and so on for example again this is still a pretty good image in terms of being nice to work with so last time I showed you this corner image so let's see where how we do with that so here again lots of nice straight lines but also lots of other stuff right so I'm not sure what to expect here I mean I guess I'm kind of sure because I did this at home but I can show you so what do we got now huh well some good news and some bad news right I mean so again there are some lines here that I trust right like I trust this big guy here and I trust this guy here because it's going through this kind of part of the building but there are lots of spurious lines right and so again it's not like this is some sort of an exact science and part of it is that yeah you could ask why didn't I pick up you know like this long line along this building and part of it is that there just didn't turn out to be the canny edge detector dot find a lot of ore as fish number pixels that were right along that one line and the other thing is that this is really looking for literally straight lines right so for some reason there's like some sort of camera distortion and those pixels don't actually lie on a really really straight line well then the Hough transform is not going to find it right has to really be truly a real straight line again there are lots of straight lines the image look of all these nice lines here the problem is that if I were to turn down my threshold to try and pick up these very short lines I'm into picking up like look at all these pixels here they're from this kind of I don't know what that is in the image it's just like stucco texture on the wall that the eye detector is picking up right and so if I was to try and find the edges of this shutter I would probably also be picking up like all sorts of crazy other Hough lines right and so the answer might be well maybe I should first do some more stringent edge detection to try and find just objects of interest I care about and then I could do like Hough transform inside a sub-region in the image that would be fine right I have to do it on the whole thing so again I could try and do better I could try to again reduce the threshold and you know we're actually in this case one guy trying to do it in here if I increase the threshold that's like saying you really have to be a good line to pass my test right so here this is a bunch you know these on these lines are accurate but I don't write so I could basically continue to try to fool around this so here this is a goalie saying that's gonna give me a bazillion lines right I'm just taking the top 50 of them but again here I do get a bunch of the true lines right all the ones that are kind of like up and down and these ones here that kind of go up to the vanishing point so if sergers that one here I got some lines that correspond it to the top edges of these windows right gave me that line so again you could also filter on the thing right you could say okay I'm expecting some lines at this orientation just find me the strongest vertical lines right finally a 50 strongest vertical lines you could do that I think I had one more example so here again an image it has lots of different kinds of lines there's lines through the ceiling tile there's line piping there's lines in this architectural ceiling and so you know let's see what we go well I certainly got a lot of crap up here and those probably came from just spurious lines I did get these lines up here in the kind of heating duct area and I got some parallel lines corresponding to parts of the ceiling tile and I got a couple of these strong lines up here in the ceiling like there's a very strong diagonal line up here and I can kind of say okay well let me turn down my we make this a little more stringent and find me really only the strong lines so if I do that you know here are some strong lines I think that except for this diagonal one I think we could all agree these are pretty good lines I'm not sure what's up with with this line but the other ones I think are reasonable again this is a pretty complicated image so I mean we tough to try to reason about the geometry of this scene I turned this down a little bit even turning it down just a tiny but tiny bit gives me starting it lots of crazy lines the part of it is that this ceiling is very textured and this piping area is very edgy and so you know there's definitely going to be some spurious lines caused by the coincidental intersection of all these edges right so so the homework asks you to play around with off transform on some images so question yeah that's a good question so could we do better by a low-pass filtering the image and maybe an example that would be my way to try it I guess I wonder whether or not the Radke of the past included an edge option in here so let's try using a LOD detector instead so I remember how do you so I definitely can use an analogy to protect her I had to pass in a threshold in a sigma so let's try it on that corner image so now I'm going off script so I'm not sure how well so let's try looking at the edges this image with the L o GE and let's just see what we get first okay so clearly I have lots of lots of edges here with the default thing so I need to use an LG that was maybe a little bit so this is telling me that this LG threshold is this high and I want to specify it I think a higher threshold and a higher Sigma to make this work so threshold let's say I want to have number one stronger images stronger image edges so maybe like let's see what you get with this okay so here here this is a little bit better in a sense that I'm only looking for really strong edges I'm wondering whether if I were to turn up the Sigma so what is the default Sigma here default Sigma is two pixels so let's see if I can turn this up to maybe how do I do this without this is why things are not sure how I can tune the Sigma and the thing at the same time so let's try a Sigma that's quite a bit bigger than before see here I have no edges all right let's not overthink this let's just make a blurrier version of that corner image that's the idea so let's make a filtered version of this image with a Gaussian or actually just make the low-pass filter because we're all in the mood to go home so let's make a blurry image and then see how that looks actually it sounds blurry so I'd like so let's make it a little bit a little bit bigger so okay so now this blurs out some texture in fact we could really go even further than this you see what good okay so let's see what would happen here I guess actually though I'm starting to run up against a problem of ringing right so I don't want to blur this with a box filter too much because I may get some sort of strange things so what I'll do question oh I'm sorry not ringing it's okay let's see what good if we do the canny know the Huff on this I don't know what's going to happen okay well that didn't work well at all actually let's just see though protected edge pixels I think what's finding it's the find the edges of this so one thing is let me turn this into a UN tape and the other thing is let me be a little bit more generous with my threshold yeah okay so here's that an example showing that if I were to blurt things out only asked for the edges that were at a very strong scale then I could expect to find you know these dark edges along the boundaries and not sure why didn't pick this one up but I guess it's because the distinction between this edge and the background is not as strong but yeah I mean this actually worked okay if I were to be a little bit more conservative even maybe I would pick up more here I was starting to make it I took a little bit too far went too far again if I was a more intelligent about having used the right balance for the loj detector for example I probably could do a pretty good job of asking for HUF edges at a certain scale right that would kind of combine we talked about last time so yeah that's a good point so if I don't want to find Huff edges in clutter then I should get rid of clutter first right okay and so next time we're going to talk about some of the stuff that we touched on today which were you know things are not perfect right so one thing is how can we clean up this edge image or clean up a binary image in general before we start to do processing on it those are called morphological operations and I've alluded to Thresh holding an image a few times we're going to talk about Thresh holding in the context of how that might help you for example find out goals okay so that's it and I will see you question you

Channel: Rich Radke

Views: 20,401

Keywords: rich radke, radke, rpi, image processing, digital image processing, edge detection, edge linking, boundary following, polygon fitting, hough transform, line detection

Id: _con6DnhkaA

Length: 77min 56sec (4676 seconds)

Published: Thu Mar 12 2015