33 Global Edge Linking using Hough Transform

you know last lecture we had an introduction on the image segmentation where we had said that the primary objective of image segmentation is through partition the given image into a number of different objects so that we can I mean Atem the results of the segmented images to have object identification and other tasks and we said that this has got extremely wide applications ranging from the target detection automated visual inspection analysis of remote sensing images and many other applications and we had also said that there are two primary approaches on the image segmentation the first is segmentation based on discontinuity detection which we had started in the last class and the second approach is based on the similarity of various pixels and we also said that in case of dynamic or time varying images one can even have the motion cues okay in order to achieve image segmentation but we have started with the image segmentation based on discontinuity of intensity values in the pixels where we had said that there are two approaches which are normally followed one is the local approach which we had decided in the last class where basically after applying any edge detector operator we were taking the H pictures and then we were grouping the H pixels according to some similarities and there we said that basic we were applying our local neighborhood practice to say our three by three or a five by five local neighborhood around the pixel of interest X Y and we were finding that in that local neighborhood whichever order these fixes were there we were finding the similarity of the eight strengths and the similarity of the age angle and grouping the pixels accordingly and we were keeping a the track by maintaining a record or list of all the pixels which can be plugged into any particular group all right and thereby our primary objective was to detect the object boundaries now this was as we say that this was primarily local because we that are using only our three by three or a five by five local neighborhood region to search for the other edge pixels and then we have said that one type of global address could be whereby we have in number of given edge points and then we were trying to fit straight lines between every pair of points and then searching that which is going to be the best fit straight line and then we said that we are going to have a such simplicity of the order of n cubed if we have to detect the straight lines out of in number of points so obviously this was computationally prohibitive and the approach which we are going to discuss now is the half transformation based approach all right now before we begin half transformation okay let us look at some very elementary concepts of it let us say that we have the XY plane like this supposing this is the X direction and this is the Y direction so this is an X small plane that we have defined and on the XY plane I take any particular point okay and let us say that the coordinate of this particular point is X why and let us also say that its intensity is f of XY now tell me that if a point XY is given to us all right then and then and supposing that XY is an H pixel and we are interested in finding out that I mean in finding out the linear is segments which are passing through this point XY now how many straight lines can pass through this point XY only four I mean assume a continuous space okay assume a continuous space I there could be infinite number of straight lines which one can draw if this is the XY point okay I can draw a straight line like this I can draw a straight line like this like this so in finite number of straight lines are possible from this point now what is the equation of the straight line since I have a let us say that the point is not XY the point is a particular point let us say X I Y I let us take a particular point whose coordinates are X I Y I and the straight line which passes through the point XY Y I that can be described by an equation like this B D is equal to a X I okay or rather we can say Y is equal to a si plus B y is equal to a X I plus B this is the equation of a straight line where a is what is that is the slope and B is the intercept now how do we obtain all these different straight lines all this infinite number of straight lines by very a and B if we vary a and B then we can draw infinite number of straight lines passing through this point X I Y I now what I am going to do I am going to write this same equation in a bit of different form okay and I will tell you how I died now the strain is same straight line equation y is equal to a X I plus B let me write it as B equal to minus X I a plus y I know big thing is there okay it's only some algebraic manipulation that I have written it as B is better minus X I a plus y I now this time now what I want to do I want to ready a and B and draw a number of freight lines now supposing I try to represent the straight line not in the XY plane but in the a B plane since we would like to keep both a and B a variable let us take this as the a axis and this as the D axis and we would like to pass a number of straight lines passing through X I Y I okay X I Y is a point which is given here and we would like to pass a number of straight lines by very a and B now tell me that how many straight lines do I get in the AV plane I am very a and B all right I will be getting only one straight line correspond to corresponding to 1 X I Y I I have got only one point X I Y Y I I started with only one point and I will be getting a straight line okay just one straight line I will be getting corresponding to the point X I Y I all right so what was a points in the XY plane has now become a straight line in the a B plane I am no longer mind Here I am no longer in the ex-wife I am right now in the uv-plane I have made a and B as variable so a and B are changing okay and accordingly my straight line is also changing alright now let us say that I have got a second point who scored in a shot is JYJ and mind you this particular straight line is unique one and only one for the point X I Y I now let us say that I have got a second point whose coordinates are X JYJ now corresponding to this particular straight line I added corresponding to this point its JYJ in the ad plane what should I get I should get yet another straight line alright so let us say that this is the straight line which we get for the point X JYJ so the the two straight lines are in general the two straight lines and meeting at a particular point okay and let us call that particular point as a I bi supposing a I bi is the point of intersection point of intersection of the two straight lines of the two straight lines in the a between is the point of intersection of the two straight lines in a ad plane now what does that indicate I'm excited for you okay and then somebody has given the correct answer actually we have got two points one point is X I Y I and we have passed the straight line to that we have got yet another point a JYJ and we have passed yet another straight line through to that and the two straight lines have intersected at some particular value of AI bi at that particular value of AI bi we are having I mean that particular value of AI bi dictates the slope and the intercept of the straight line which passes through a sigh why I and X 0 Y G in the XY plane so now the picture is something like this if I draw the XY plane okay I have got two points one is X I Y I and the other point is its J YJ and the two straight lines and N and and the middle is a straight line passing through these two points X I Y I and XJ YJ and in the AV plane we are having one straight line like this another straight line like this and they intersect at a point which is known as the AI bi so obviously AI bi is a point in the a B plane and a point in the a B plane becomes what in the XY plane in becomes a straight line in the XY plane this is a point a I bi it becomes a straight line in the XY plane and a point in the XY plane becomes a straight line in the a B plane alright so now what we will do that instead of trying to process the image in the xy-plane we will try to process the image in the KB plane okay and we will see that why should we do that and what is the advantage that we are trying to get in that process why going to be remain in XY plane in order to detect the straight line we are not doing that we are going over to the a B plane and let us first tell you that what is the principle behind it okay but how exactly we do that okay that's what we are going to discuss now please note here that every check line in the XY plane will get mapped to a point in the a B plane all right now that means to say that if there are I mean if if we have a number of points let's say we have got a number of collinear points on this straight line a large number of collinear points now this will give rise to what in the a B plane correct this will give rise to one point with lots of lines passing through inch now if it is possible for me to give account of how many lines are passing through this particular point in the any plane okay then that it is what supposing I find that in number of straight lines are pass through a particular point a I bi in the a B plane what does that mean in the XY plane number of points in the XY plane alright so what happens that every point will get mapped into a straight line in the AV plane and let us say that how we are going to tackle this problem in the discrete space because after all we are not going to operate in the continuous domain we are going to operate in the discrete domain where all the values of a and B will not be allowed but only a discrete set of values of a and B will be allowed so what we will do supposing we draw the a B plane okay in an enlarged form like this okay and let us say that we have these many partitions for a ok and let us say we have similarly a large number of partitions for B okay and we will be allowing only the discrete values of a and B that means to say a can be either one unit two units a unit for unit like this and if I mean this is the axis I mean if I mean this is the origin 0 0 then even B also can have all the discrete set of values which are shown over here now what we will do when we detect a particle I mean when we have any particular points in the XY plane I have already said that that will get mapped into our I mean a point in the XY plane will get mapped into a straight line in the ad plane so what we will do we will apply the equation b equal to minus x i a plus y i and then what we are going to do we we are given with a particular x iy i that x YY is given to us and now we will keep on bury a we will first take a equal to 0 and see what value we get far be ok supposing we have taken supposing this is this bin is for a is equal to 0 for 4 equal to 0 this is the column equal to 1 this is the column is equal to 2 this is the column like this and this is for B equal to 1 B equal to 2 B equal to 3 like this ok now when I find that corresponding to a is equal to 1 the value of B is let us say over I mean let us say the value of B is something like this I mean somewhere over here we will be incrementing that particular cell supposing we have gone I mean we have divided this entire ad space into a large number of cells supposing we have K number of partitions for a and L number of partitions for B so we have divided the entire a B space into K into L number of cells so we have chosen value of a equal to 1 and find out that what is the containing value of B that we calculate from this equation and corresponding to that value of V we will be incrementing that cell initially we will clear all these cells we start with all the cell's initialize to 0 where we are going to keep them they take a count on how many times the accumulator cells okay will be incremented is this problem clear to you we have a large number of accumulator cells okay for a we have made K number of partitions for D we have made L number of partitions so really speaking there are K into L number of accumulator cells and initially we are clearing all the accumulator cells so every cell value is kept to zero initially now we are taking the point XY Y I okay the first point is X Y is the first point is X I Y I and we now begin with a equal to 1 the first column okay we take the first color substitute a equal to 1 and get a value of B so that particular AV cell is incremented okay then again go over to the next value of pain okay if you had started with a equal to 1 okay the next value of K will be equal to 2 corresponding to a equal to 2 find out what BTS supposing we have got B equal to one over here supposing now we go over to a equal to 3 and find that the corresponding value of B is here so we increment that cell all the other girls are having a value equal to 0 come to next the value is 1 come to next the value is 1 like this supposing we keep on cleaning up okay and we have got I mean the accumulator condition now like this all right then we find a second point okay let us say the second point is XJ YJ corresponding to the second point there will be yet another straight line all right and supposing that straight line and for that straight line supposing when area when I substitute B is equal to minus XJ a + YG ok then corresponding to this X JYJ I will again start with a equal to 1 alright and I will get a different value of B isn't it supposing the value of B is over here come to be equal to 10 and then come to a equal to 2 we get the corresponding value of this somewhere here come to is equal to C supposing this is the point which we get now already this point is having account equal to 1 so now the count will become 2 and the other cells will get incremented corresponding to X JYJ all right now we take the third point which is say X M Y M corresponding to XM ym there will be yet another straight line that will cost suppose e-111 this cell will get in term ended and become 3 1 1 1 now if we examine this cell array after I mean after substituting the equation for 3 3 X we would see X Y points okay I took X I Y I I took XJ YJ I took XM YM after taking the reserved these 3 points okay the situation of the accumulator is somewhat like this what is the significance after examining this a b-cells okay after examining the cells in the ad plane what I find is that at this particular point okay we are having a pick equal to three okay and this indicate that through this point okay in the ad plane I have passed I mean this count is three this the count of three has come because I have got three three points okay which having through which I can pass the straight line I mean if the field I mean if this three points happened to be collinear points okay then I will be having count of three here so this corresponds to this particular value of a be indicating that there are three points or the other three straight lines passing through this particular point all right so what we will do we will keep on picking up we will keep on picking up the cells which are having high counts alright is this approach clear to you okay so I again repeat what I did I took X I Y I and found out that which beans are getting accumulated which cells are getting accumulated I do get another point XJ YJ so how many cells are accumulating again I took a third point XM YM so how many cells got accumulated like this I can go okay for a large number of edge points typically we will be having n number of edge points okay and we will be incrementing the cells corresponding to this particular equation okay given by this equation will be incrementing sells and we will be picking up those cells which are having large number of Tom's if I get a count of three what does that really indicate count of three indicates that three points have contributed to a straight line okay count of one indicates that only one point has contributed to a straight line so this is not a real straight line but says three points haven't contributed to a straight line we can say that this is a genuine straight line since 3h points are contributed to this okay and if I have n number of each points okay which which are collinear if we have n number of collinear edge points then we will be having account equal to n for this particular bin is this understood very clearly now the pertinent question is that how many divisions do we make for a and B how many cell divisions do we make what is the range of a and B definitely we have to draw the accumulator cells for a that I mean four values of a within the limits a mean and a max where a mean is the minimal value of slope and a max is the maximum value of slope and similarly the range of B is B mean for minimum value of intercept and V Max for maximum value of intercept okay so within the range a mean to a max I will be dividing a into K number of cells and within the limits be mean to be max I will be dividing the B axis into L number of cells so that I have totally K into L number of cells that tell me what is a mien and BB Amy is a min is okay I mean considering the magnitude part of the snow okay evening they magnitude value of a mean could be 0 okay what is going to be V mean do okay okay if we consider the magnitude part okay what is going to be a max in highlight B max infinity and if you don't take the magnitude part you take both magnitude assign then the range of M into M X is minus infinity to plus infinity the range of V need to V Max is minus infinity to plus infinity so do you think that whatever we have discussed is feasible whatever we have discussed is absolutely not feasible because in combinations I cannot have limits ranging from minus infinity to plus infinity or I mean forever flows as well as for intercept but really speaking of such situations will arise what happens when we have a vertical line and vertical line we are where I am going to have vertical lines will be there any ranges so this was unavoidable so there is no point in doing any kind of approximation or things like that okay we really cannot implement this thing in practice our XY domain was not friendlier the XY domain was much better as compared to this new ad space which we have created okay you know some are not agents of this able clean after all when we are trying to detect straight lines globally in the spatial domain we had indicated okay in the earlier class we have discussed that we are going to have order of n cube number of computations to detect a straight line okay whereas in this case okay how many number of searches are involved totally for L in all right the total space is n square okay no doubt but in order to search for a particular straight line okay what we are going to do we are I mean just exact I will be able to examine the cells for every a okay this a this is they say and how many such a that there there are K number of cells and for n number of points we are going to search it for K into n okay so the order of the search is kN okay so we have reduced the search space for detecting straight lines so this is computationally possibly easier but implementation wise we have a difficulty so one can always argue that parameter space has got some benefits no doubt because if instead of going from the original XY space to this a B is no ever parameter space this ad plane we are describing it as the parameter space so in the parameter space the number of I mean the searching for straight line is obviously simpler okay we have order of n number of searches but we find that there is a difficulty that in the range minus infinity to plus infinity we have to accommodate the cells this is for a and for B again the range is minus infinity to plus infinity so what we do do we so away the parameter space and set let us keep the parameter space concept okay and say that in what alternative manner we can write a straight line okay we have the straight line supposing we have a straight line in the XY plane and the straight line is like this now what we can do from the origin we can draw a perpendicular on this XY and supposing the length of this perpendicular is Rho okay the length of this perpendicular is Rho and the angle which we press from this axis we are calling that angle as theta okay so this is our perpendicular and Rho is the perpendicular length and theta is the angle okay so what is going to be the equation of this straight line in terms of Rho and theta it does of ramp it up if we specify Rho and theta the straight line is uniquely specified isn't it the straight line is uniquely specified in the XY plane so what is going to be the straight lines equation Rho is equal to X cos theta plus y sine theta in earlier case we were taking the equation as y is equal to a X plus B and in this case Rho is equal to X cos theta plus y sine theta now get this first question x and y will be interchange to or one minute and yes yes yes you're right absolutely yeah we will be defining the there will be minor x-axis this way let us have this as the x-axis and the y-axis and now the equation is R is equal to a star theta plus y sine is definitely okay thank you for this correction now in this if I take any point in the XY plane okay what does that correspond to the Rho theta plane so now our parameters R Rho and theta naught a and B the parameters are going to be Rho and theta so from the XY space we will be going over to the Rho theta space so if I have a point in the XY plane okay what does that mean in the rosita plane is it a line a straight line circle anybody else this is a lie on a table that's a color talk about nature of sinusoidal nature isn't it okay it gives rise to sidesaddle company because the equation is X cos theta plus y sine theta so it gives rise to sinusoidal curves all right so any point in the XY plane will be mapped into a sinusoidal curve in the road eater plane and if I have aa number of collinear points in the XY plane what'll that mean in the repeatably I will get efficient I have got an outer pulley here points in the XY plane what should I get in the parameter row feet of space I will get same curves okay but the curve will pass through but again these curves are going to intersect at a particular point if I have n number of collinear points in the XY plane all right they are going to intersect okay at the same point okay in number of times there will be and then we will be having I mean if I take n number of points from the XY plane in the Rho theta space supposing this is our road and this is our theta all right and we are going to have for one point we are going to have a curve like this for another point we are going to have a curve like this for another point we are going to have a curve like this okay and if there are n number of points then the point of intersection will indicate what the point of intersection a particular row I theta I through which how many counts should pass n number of curves should pass through Rho I theta I in the parameter space alright okay crystal is nice one minute one minute I will let me clear the concept further we have taken our straight line in the XY plane okay and the straight lines equation is described as Rho is equal to X cos theta plus y sine theta where Rho is the perpendicular distance from the origin and theta is the angle with respect to the x axis okay now my parameter saw Rho and theta and we are now going over to the row feature of space instead of being in the XY space all right now I take a particular point let us say I take x1 y1 okay I take a point x1 y1 and corresponding to that point okay what I will do I will decide on a particular value of theta okay and compute row according to this it's cos theta X 1 cos theta plus y 1 sine theta okay and then I will be varying theta I mean for a particular value of theta I get a particular value of Rho again for the next value of theta I get next value of flow like this I will be tracing a call all right so I trace a curve so what was our point in the XY plane becomes a sinusoidal curve in the rosita space it becomes all sinusoidal got in the rosita space I take the second point x2 y2 and by taking that second second point I will be tracing I will just in God as it is in yet another car okay and what does the point of intersection of this cube curves mean tell me the physical concept of that that means to say that that particular row I theta I which is the intersection okay corresponds to the value of Rho theta which I get by the by by joining the points x1 y1 and x2 y2 okay if I join I mean I take the XY plane okay and I join x1 y1 and x2 y2 okay it is going to have some value of Rho theta and that is that well you know whether it is revised you die all right so the point of intersection gives me that value of Rho theta which passes through and I mean the value of procedure corresponding to the straight line joining x1 y1 and it's through Y 2 now instead of two points if I have n number of collinear points I have got n number of collinear points whose coordinates are x1 y1 x2 y2 is cetera etcetera up to X n xn yn then for each of these points I will be having one sinusoidal curve okay and since they are collinear points there is a real straight line that process through this point this n number of points in the XY plane so it is going to have one particular unit value of Rho and theta that take line in the XY plane so all these n collinear points okay will give rise to n number of curves in the Rosetta space and those curves will intersect at the particular value of Rho theta which is the row theta for the straight line talking through this in number of points is this clear to you now right so again the concept is very similar we are going to examine the row feature cells so the entire so we are going to divide the row teach our plane into a number of cells ok supposing this is the direction or row okay and this is the direction of theta then we have a large number of graffiti ourselves like this okay and we are going to examine what those cells which are going to have high values come okay high values of counting to get those many number of collinear points okay aren't there okay and we can group them into straight line alright so if I have a value of I mean if I get some high value of count on this accumulator cell and on this accumulator cell and possibly on some other accumulator cell over here okay and very low value of counts or the other cells what does it indicate there are three different cell lines which are there okay so tell me one thing that if in the XY plane supposing this is X and this is point in the XY plane if I have two straight lines like this okay and I have chosen the straight line so that both these two straight lines line number one and line number two are having the same value of Rho and theta okay so what should I get in the parameter space if I have in one number of collinear points corresponding to segment line segment number one and if I have in two number of points corresponding to line segment number two okay what is the count that I am going to get in the cell corresponding to that particular row I theta I and 1 plus in to cut from that what should I in physically there are two straight lines but I will infer that there are that there is only one straight line contributed by n1 plus into number of pixels so what should I do just keeping a record of the accumulated count is not enough we have to also see that and we have to keep a record of which pixels are contributing to that cell come ok and we will also maintain a list of all the pixels which are contributing to the incrementing of that particular accumulator cell so if I can record all the n1 pixels coming from line segment number one and all the into pixels which are coming from line segment number two in this case what I will do later on is I will examine the coordinates of all these pixels and find that since the coordinates of these line segments and the coordinates of pixels belonging to this line segment are widely different okay physically they mean two different straight lines okay it can easily happen let me tell you something I have some industrial object okay which is having a shape like this supposing I have got an industrial object of this ship okay this is a straight line this is a straight line and that and these two are having identical Rho and theta values okay but if I examine these set of Texas coordinates of these pixels and coordinates of these pixels okay I can clearly see that these belong to one straight line and this belong to a second straight line now supposing I mean in the last class I was mentioning about a problem that when you are trying to detect the age for an image which is having a very poor contrast okay you will observe what you'll of the brace in the line segments okay so supposing for an object of this nature okay you are getting the H pixels of this fall there are some gaps like this okay so in this case what can you do you can simply breathe the gas okay so that means to say that by examining the contributing XY pixels to a given accumulator cell in the row theta space okay we can see that if the X Y values are widely different okay then they correspond to two different line segments otherwise if they are close enough to each other then all of them can be grouped into a single straight line segments like here I could be having some small small gaps I could be having one two three four five such gaps okay but all these gaps are very small so that if I take the coordinates of all these contributing pixels okay I can ultimately detect that this is one on the same as saying that we had a straight line running from this end point to this end point all right so thereby in the detected line segment we will not be having any breaks because I discuss in the last class that having such discontinuities in the line segment okay becomes a very severe problem in detecting the object boundaries is that understood now let me summarize the various steps okay which we are doing okay at first so edge linking based on Hough transform at first we compute the gradient of an image compute the gradient of any weight or whether you detect the a signals okay detect the H pixels this is for the detection of H pixels all right and after detecting the HP cells you specify the subdivisions in the XY plane the subdivisions in a row theta plane and then in the third state you examine the counts of Rho theta accumulator for high pixel concentrations and in the fourth step you examine the continuity between pixels in a chosen cell okay so if we carry out all these four steps okay we can detect the individual line segments which are present in an image starting with a given set of edge pixels all right so all these incrementing accumulator array and all these things we have to do for by considering every such H pixels is that clear to you so wherever we have such noisy pictures wherever the H pixel does not correspond to any object okay it just corresponds to a noise in that case for those eight speech cells we will be having lower value of accumulator counts okay let us four collinear points okay they will give rise to high accumulator values okay for the corresponding value of Rho theta all right so we will be discussing about other approaches to image segmentation in the next class thank you I wasn't

Channel: kashyap B

Views: 25,413

Keywords:

Id: koLqyacnZA4

Length: 53min 35sec (3215 seconds)

Published: Fri Jun 28 2013