🚀 go-pugleaf

In article <1993Jan21.192619.10241@pinet.aip.org> scotj@pinet.aip.org (scot_shinderman) writes:


>    While reading the standard image processing books I have noticed one
> algorithm that seems to be glossed over: contour tracing.  In the
> pictures that I am scanning, a filter is run across the pixels and a
> threshold is applied to produce either white or black pixels for the
> grey-scale.  At this point there is usually a rather disconnected set of
> dots due to noise in the picture but also some strong edges from the
> filter.  What is the "pratical" method of moveing along the detected
> pixels to find lines (or curves).  If I try to step from one pixel to
> the next by looking in a neighborhood, then the path almost always gets
> caught up in the noise off to one side or another.  Is there a way to
> "nudge" the search in a particular direction based on previous motions.
>   Any suggestions (or sample code!) would be greatly appreciated.

Just off the top of my head.  Have you considered trying to use some
iterative deepening backtracking procedure (algorithms like A*)
heuristically guided by some bayesian probability of the type of curve
which you are expecting to see?

-Patrick






--
-------------------------------------------------------------------------------
Patrick Cheng-San Teo                                       teo@cs.stanford.edu
Department of Computer Science                      
Stanford University                                  Home Phone: (415) 424-0330

"Everything should be made as simple as possible, but not simpler"
-- Albert Einstein
-------------------------------------------------------------------------------

Hysteresis is one common technique, often used as a back end to edge
detectors. There's probably more information in the machine vision
literature than in mainstream image processing literature.

Rick 

--
In article <1993Jan21.192619.10241@pinet.aip.org>, scotj@pinet.aip.org (scot_shinderman) writes:
[...]
|>   While reading the standard image processing books I have noticed one
|>algorithm that seems to be glossed over: contour tracing.  In the
|>pictures that I am scanning, a filter is run across the pixels and a
|>threshold is applied to produce either white or black pixels for the
|>grey-scale.  At this point there is usually a rather disconnected set of
|>dots due to noise in the picture but also some strong edges from the
|>filter.  What is the "pratical" method of moveing along the detected
|>pixels to find lines (or curves).  If I try to step from one pixel to
|>the next by looking in a neighborhood, then the path almost always gets
|>caught up in the noise off to one side or another.  Is there a way to
|>"nudge" the search in a particular direction based on previous motions.
[...]

1)	You can try to fix some "small gaps" in your lines by morphological 
	operations ( n times dilate and afterwards n times erode, where 0<n<6 ).
2)	You can use a Hough-Transform to get clues, where to find lines (or curves)
	in the image.
3)	You can use a sort of relaxation method to extract the lines, but to do
	this you can not simply threshold your filter output.
4)	You can extract line parts as a symbolic description of the connected
	components of your binary image and join line parts to lines (or curves)
	by symbolic methods
	
----------------------------------------------
Torsten Ihle, cand. inf., TU-Dresden
EMail: ihle@iki101.inf.tu-dresden.de

Es ist deutsch in Kaltland !
----------------------------------------------

In article <TEO.93Jan21203514@Xenon.Stanford.EDU> teo@cs.Stanford.EDU writes:
>In article <1993Jan21.192619.10241@pinet.aip.org> scotj@pinet.aip.org (scot_shinderman) writes:
>
>
>>    While reading the standard image processing books I have noticed one
>> algorithm that seems to be glossed over: contour tracing.  In the
>> pictures that I am scanning, a filter is run across the pixels and a
>> threshold is applied to produce either white or black pixels for the
>> grey-scale.  At this point there is usually a rather disconnected set of
>> dots due to noise in the picture but also some strong edges from the
>> filter.  What is the "pratical" method of moveing along the detected
>> pixels to find lines (or curves).  If I try to step from one pixel to
>> the next by looking in a neighborhood, then the path almost always gets
>> caught up in the noise off to one side or another.  Is there a way to
>> "nudge" the search in a particular direction based on previous motions.
>>   Any suggestions (or sample code!) would be greatly appreciated.
>
>Just off the top of my head.  Have you considered trying to use some
>iterative deepening backtracking procedure (algorithms like A*)
>heuristically guided by some bayesian probability of the type of curve
>which you are expecting to see?
>
>-Patrick
>
>-------------------------------------------------------------------------------
>Patrick Cheng-San Teo                                       teo@cs.stanford.edu
>Department of Computer Science                      
>Stanford University                                  Home Phone: (415) 424-0330
>
>"Everything should be made as simple as possible, but not simpler"
>-- Albert Einstein
>-------------------------------------------------------------------------------

Do we really need these kinds of answers wasting net bandwidth?

Stick to the motto in your by-line and offer constructive advise, please.

In article <1993Jan21.192619.10241@pinet.aip.org> scotj@pinet.aip.org (scot_shinderman) writes:

      While reading the standard image processing books I have noticed one
   algorithm that seems to be glossed over: contour tracing.  In the
   pictures that I am scanning, a filter is run across the pixels and a
   threshold is applied to produce either white or black pixels for the
   grey-scale.  At this point there is usually a rather disconnected set of
   dots due to noise in the picture but also some strong edges from the
   filter.  What is the "pratical" method of moveing along the detected
   pixels to find lines (or curves).  If I try to step from one pixel to
   the next by looking in a neighborhood, then the path almost always gets
   caught up in the noise off to one side or another.  Is there a way to
   "nudge" the search in a particular direction based on previous motions.

Here are some references:

@STRING{pami = {IEEE Transactions on PAMI}}
@STRING{scia87 = {Proceedings of 5th Scandinavian Conference on Image Analysis, Stockholm (Sweden)}}
@STRING{prl = {Pattern Recognition Letters}}
@STRING{cgip = {Computer Graphics and Image Processing}}
@STRING{cg = {Computer Graphics}}

%		--------------------------------
@INPROCEEDINGS{giraudon87a,
	AUTHOR = {G. Giraudon},
	TITLE = {{An Efficient Edge Following Algorithm}},
	YEAR = {1987},
	BOOKTITLE = scia87,
	VOLUME = 2,
	PAGES = {547--554}
}
%		--------------------------------
@ARTICLE{meer90b,
	DATE = {Fri Jun 15 1990},
	AUTHOR = {P. Meer and C. Allen Sher and A. Rosenfeld},
	TITLE = {{The Chain Pyramid: Hierarchical Contour Processing}},
	YEAR = {1990},
	JOURNAL = pami,
	PAGES = {363--376},
	NUMBER = {4},
	VOLUME = {12}
}
%		--------------------------------
@ARTICLE{xie92a,
	DATE = {Tue Mar 10 1992},
	AUTHOR = {M. Xie and M. Thonnat},
	TITLE = {{An Algorithm for Finding Closed Curves}},
	YEAR = {1992},
	JOURNAL = prl,
	PAGES = {73--81},
	NUMBER = {1},
	VOLUME = {13}
}
%		--------------------------------
@ARTICLE{xie92b,
	DATE = {Mon Nov  2 1992},
	AUTHOR = {M. Xie},
	TITLE = {{Edge Linking by Using Causal Neighborhood Window}},
	YEAR = {1992},
	JOURNAL = prl,
	PAGES = {647--656},
	VOLUME = {13},
	MONTH = {September}
}
%		--------------------------------
@ARTICLE{chakravarty81a,
	DATE = {Wed Dec  2 1992},
	AUTHOR = {I. Chakravarty},
	TITLE = {{A Single-Pass, Chain Generating Algorithm for Region Boundaries}},
	YEAR = {1981},
	JOURNAL = cgip,
	PAGES = {182--193},
	VOLUME = {15}
}
%		--------------------------------
@ARTICLE{rosenfeld78a,
	DATE = {Fri Dec 11 1992},
	AUTHOR = {A. Rosenfeld},
	TITLE = {{Algorithms for Image/Vector Conversion}},
	YEAR = {1978},
	JOURNAL = cg,
	PAGES = {135--139},
	VOLUME = {12},
	MONTH = {august}
}
--
Karl Tombre - INRIA Lorraine / CRIN-CNRS     --- Email: Karl.Tombre@loria.fr
Post: Batiment LORIA, BP 239, 54506 Vandoeuvre CEDEX, France --or--
      615 rue du jardin botanique, BP 101, 54602 Villers CEDEX, France
Phone: +33 83.59.20.71 --- Fax: +33 83.41.30.79  --or-- +33 83.27.83.19

In article <1993Jan21.192619.10241@pinet.aip.org>, scotj@pinet.aip.org (scot_shinderman) writes:
|> 
|>    While reading the standard image processing books I have noticed one
|> algorithm that seems to be glossed over: contour tracing.  In the
|> pictures that I am scanning, a filter is run across the pixels and a
|> threshold is applied to produce either white or black pixels for the
|> grey-scale.  At this point there is usually a rather disconnected set of
|> dots due to noise in the picture but also some strong edges from the
|> filter.  What is the "pratical" method of moveing along the detected
|> pixels to find lines (or curves).  If I try to step from one pixel to
|> the next by looking in a neighborhood, then the path almost always gets
|> caught up in the noise off to one side or another.  Is there a way to
|> "nudge" the search in a particular direction based on previous motions.
|>   Any suggestions (or sample code!) would be greatly appreciated.
|> - thanks!
|> - scot shinderman (scotj@aip.org)

Here are some more references:

%A I. Sobel
%T Neighborhood Coding of Binary Images for Fast Contour Following and General Binary Array Processing
%J Computer Graphics and Image Processing
%V 8
%I Academic Press, Inc.
%C New York
%D 1978
%P 127-135

%A T. H. Morrin
%T Chain-Link Compression of Arbitrary Black-White Images
%J Computer Graphics and Image Processing
%V 5
%I Academic Press, Inc.
%C New York
%D 1976
%P 172-189

%A P. E. Danielsson
%T Encoding of Binary Images by Raster-Chain-Coding of Cracks
%J IEEE Proc. Int'l Conf. on Pattern Recognition and Image Processing
%D 1982

%A C. Ronse
%A P. A. Devijer
%T Connected Components in Binary Images: the Detection Problem
%I Research Studies Press
%C Letchworth, England
%D 1984

%A D. W. Paglieroni
%A A. K. Jain
%T Contour Control Point Algorithms for Shape Measurement and Inspection
%J SPIE Conference on Advances in Intelligent Robotics Systems
%C Cambridge
%D October 1986

-- 


	Iskender Agi		
	Computer Science Laboratory
	SRI International
	iskender@csl.sri.com