From: Chris Russ Subject: Re: Help! Broken fixing lines for image recognition? Date: 14 May 1999 00:00:00 GMT Message-ID: <373C571E.B9000A3E@aol.com> Content-Transfer-Encoding: 7bit References: <373c65f8.3073455@news.rdc1.on.home.com> X-Accept-Language: en X-Notice: should be reported to postmaster@ibm.net Content-Type: text/plain; charset=us-ascii; x-mac-type="54455854"; x-mac-creator="4D4F5353" X-Complaints-To: postmaster@ibm.net X-Trace: 14 May 1999 17:05:10 GMT, 166.72.184.143 Organization: Reindeer Games, Inc. MIME-Version: 1.0 Reply-To: jcr6@aol.com Newsgroups: comp.graphics.algorithms,sci.image.processing Henry Liu wrote: > Hi, > I've been working on object detection and basically I've finished an > edge detection/filtering technique that works quite well to generate a > black and white only border of an image. However after the edge > detection, quite a few of the lines are broken. I'm trying to detect > any object that looks relatively thin and is long (ie like a thick > string that runs across the image). I'm trying to use a simple > dilation but that doesn't seem to be feasible since multiple lines are > usually close together. If one follows a line by hand, one can easily > extrapolate by looking at the slope continuities to fill in a missing > segment. I was wondering if there was an available algorithm that > traces lines and if a broken part is found, it simply fills it in by > joining to a segment that has a similar slope deeper along the path? > I've been trying to use bwlabel to label objects in matlab but of > course it chokes since the objects are closed. Is there something > that does the opposite of breaking apart by erosion? There are more > than one or two pixels between broken lines however so the 'bridge' > function doesn't seem to do much. Any help would be greatly > appreciated. Please e-mail me at henry.liu@utoronto.ca if you can > help so that I don't miss any posts. Thanks. Henry, This is a common problem, but you have to make a couple of assumptions about the line breaks that you're trying to fill: 1) That there isn't a whole lot of salt/pepper noise that can cause things to grow together that shouldn't 2) that lines tend to have low curvature. One method is to try to bridge gaps of one pixel. Build a 256-entry table that consists of the following data: the index is 0..255 from summing up the neighbors that are on: 1 2 4 256 x 8 128 64 16 So a neighborhood (around a white pixel) like this: 1 1 0 0 x 0 0 0 1 would have an index value of 1+2+16 = 19. Thus, the table you build would have a TRUE in it at index 19. This means that this pixel should be turned on... By populating the rest of the table with rules for "Conditional Dilation" or "Morphological Dilation" you can bridge small 1-pixel breaks in lines. If you've got bigger breaks there's a problem. Obviously you could try to use a 20-neighbor octagonal area, but that gets pretty big. Or, you could try to project the existing lines that you have by a pixel in the correct direction by iterating and marking the new pixels. Once you've grown by a reasonable amount (what is reasonable?) any new growth that connects lines together can stay, but any new growth that didn't connect to something else should be removed. How do you project a line? If you have a simple pattern like this: 0 0 0 1 1 0 0 0 0 It is pretty obvious what pixel should be turned on next. However, if you have something that exhibits jaggies like this: 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 <- Grow here? 0 0 0 0 0 <- or grow here? 0 0 0 0 0 we have to start looking at larger neighborhoods to figure out which way the line is running to connect the lines better. I used a different approach entirely at ADE Optical Systems (we were looking at scratches on Silicon Wafers). If you make a poly-line (in our case an array of 16 points), it is relatively easy to project the line (including the local curvature) for where a hypothetical 17th point would be. By iteratively growing and seeing what merges, we can connect lines that belong together (and lines that do not). This is not a simple problem. -Chris Russ