Browse Prior Art Database

Boundary Extraction Method and Algorithm

IP.com Disclosure Number: IPCOM000075488D
Original Publication Date: 1971-Sep-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 3 page(s) / 65K

Publishing Venue

IBM

Related People

Chow, CK: AUTHOR [+2]

Abstract

This is a means and algorithm to calculate thresholds to determine boundaries for low-quality pictures, for which available methods are ineffective.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 3

Boundary Extraction Method and Algorithm

This is a means and algorithm to calculate thresholds to determine boundaries for low-quality pictures, for which available methods are ineffective.

Fig. 1 shows a functional block diagram of the method. A scanner scans a picture such as an X-ray picture, and outputs a video signal. Then the signal is quantized by the quantizer and the quantized signal is fed into a digital computer. The signal processed by the computer is displayed on a display unit or transmitted to other devices.

The algorithm implemented in the computer consists of the following major steps: 1) Divide the entire picture in a set of smaller, overlapping regions; 2) Compute the histogram for each region: 3) For each computer histogram, estimate the component distributions and coefficient of mixture of two distributions,; 4) Test the resultant mixtures for bi-modality; 5) For every histogram with appreciable bi-modality, calculate the threshold from the estimated distribution by the Method of maximum likelihood; 6) Interpolate from the threshold calculated in (5) the thresholds for all image points; and 7) Perform a binary decision for each image point using the threshold obtained in (6). A Computer Program.

Fig. 2 shows a flowchart of a computer program based on the principle described above. Each box is denoted by a step number. First, logarithmic operation (2) is carried out on the digitalized picture (1). In step (3), the entire region is divided into say, 49 regions as is shown in Fig. 3. Then 49 histograms are computed at step (4). Step 5 is a curve fitting procedure to be carried out for all the 49 histograms so as to estimate the component distributions. The histogram at the r-th region is fitted by:

(Image Omitted)

where p(1r) and p(2r) correspond to the fractions of areas of the r-th region occupied by the background and the object, respectively: mu(1r) and sigma(1r) correspond to the mean and variance of the normal distribution associated with the background in the r-th region while mu(2r) and sigma(2r) are those of the object. p(1r) + p(2r) = 1. Each of the computed histograms is least square fitted with the sum of normal curves shown in (A) by adjusting the five parameters p(1r), mu(1r), mu(2r), sigma(2r) and sigma(2r). After the curve fitting procedure at step (4), the shape for each of the sums of two resultant normal curves is examined by the following three conditions:

(Image Omitted)

The thresholds, sigma(o) , mu(o) , epsilon(o) , may be set a priori using knowledge on experiments. Or they may be calculated adaptively to a given picture by such method that only a fixed number, say 20, can pass each of the three conditions.

At the end of step (6), some regions are assigned computed thresholds, and the others are not. At step (7) thresholds for the latter are interpolated from the

1

Page 2 of 3

computed thresholds of their neighboring regions. Let t(m,n) be the calculated threshold at the region (m,n), wher...