Browse Prior Art Database

Multiple Curve Detection Using the Minimal Description Length Principle and the Hough Transform

IP.com Disclosure Number: IPCOM000122681D
Original Publication Date: 1991-Dec-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 6 page(s) / 293K

Publishing Venue

IBM

Related People

Dom, BE: AUTHOR [+3]

Abstract

Disclosed is a technique for detecting curves in a noisy image using an information measure based on the code length required to encode the data contained in the output of an edge detector using encoding schemes based on certain probability models. The technique described here represents an advance over traditional techniques that use the Hough transform (HT) with an arbitrary threshold and over robust curve-fitting techniques that are incapable of coping with multiple unknown numbers of curves. The image represents some scene in which there are curves (e.g., the natural boundaries of objects), and the edge detector outputs a binary image with the black pixels representing locations where edge points were detected.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 21% of the total text.

Multiple Curve Detection Using the Minimal Description Length Principle
and the Hough Transform

      Disclosed is a technique for detecting curves in a noisy
image using an information measure based on the code length required
to encode the data contained in the output of an edge detector using
encoding schemes based on certain probability models.  The technique
described here represents an advance over traditional techniques that
use the Hough transform (HT) with an arbitrary threshold and over
robust curve-fitting techniques that are incapable of coping with
multiple unknown numbers of curves.  The image represents some scene
in which there are curves (e.g., the natural boundaries of objects),
and the edge detector outputs a binary image with the black pixels
representing locations where edge points were detected.  Due to noise
and to spatial and gray- level quantization effects, there will be
spurious points not associated with any real edge (these points are
referred to as "background noise points"), and the detected real edge
points will, in general, be displaced from their true locations.  The
important new contribution described here is a new criterion that
enables the distinction between background noise points and curve
points, as well as locating the curves and their endpoints. The
method is subsequently extended by enabling it to also utilize
gradient information in order to improve its performance.
MINIMAL DESCRIPTION LENGTH (MDL) CRITERION FOR BINARY EDGE DETECTORS

      Let u(i) e {black, white} take the binary value of pixel i with
i = 1,...,N being some indexing of the pixels and N representing the
total number of pixels in the image. Let U = {u(1),...,u(N)} and let
model M(k) (k = 1,2,...) represent a set of curves C(k) e C and a
proper parameterized probability function p(U|k,t(k)), where C is a
family of curve sets representing all the possible combinations of
parameterized curves in the given image. The parameter set t(k) =
(tc(k),tp(k)) consists of the parameters tp(k) needed to fully
specify the probability functions, and the parameters tc(k) needed to
delinate the curves.  The minimal description length of the image
using model M(k) is given by:
      MDL(k) = Min {-log p(U|k,t(k)) + Dc(k) + Dp(k)}
where the minimum is over all t(k) e T(k).  Dc(k) denotes the
description length of the curves, and Dp(k) denotes the description
length of the parameters of the probability model.  According to the
universal prior (1): Dc(k) = 1/2Kc(k) log N, and Dp(k) = 1/2Kp(k) log
N, where Kc(k) and Kp(k) denote the number of free parameters in
tc(k) and tp(k), respectively.

      The minimal description length of the image using the whole
family of models is given by:
      MDL = Mink{MDL(k)} = Min {-log p(U|k,t(k)) + Dc(k) + Dp(k)}  (1)
where the (second) minimum is taken over all k and t(k) e T(k).  This
forms the basic formula for curve detection. The estimates for the
curves are determined by the op...