Balanced histogram thresholding

Last updated

In image processing, the balanced histogram thresholding method (BHT), [1] is a very simple method used for automatic image thresholding. Like Otsu's Method [2] and the Iterative Selection Thresholding Method, [3] this is a histogram based thresholding method. This approach assumes that the image is divided in two main classes: The background and the foreground. The BHT method tries to find the optimum threshold level that divides the histogram in two classes.

Contents

Original image. Lovely spider.jpeg
Original image.
Thresholded image. Lovely spider BHT.jpeg
Thresholded image.
Evolution of the method. BhaProgress3.gif
Evolution of the method.

This method weighs the histogram, checks which of the two sides is heavier, and removes weight from the heavier side until it becomes the lighter. It repeats the same operation until the edges of the weighing scale meet.

Given its simplicity, this method is a good choice as a first approach when presenting the subject of automatic image thresholding.

Algorithm

The following listing, in C notation, is a simplified version of the Balanced Histogram Thresholding method:

intBHThreshold(int[]histogram){i_m=(int)((i_s+i_e)/2.0f);// center of the weighing scale I_mw_l=get_weight(i_s,i_m+1,histogram);// weight on the left W_lw_r=get_weight(i_m+1,i_e+1,histogram);// weight on the right W_rwhile(i_s<=i_e){if(w_r>w_l){// right side is heavierw_r-=histogram[i_e--];if(((i_s+i_e)/2)<i_m){w_r+=histogram[i_m];w_l-=histogram[i_m--];}}elseif(w_l>=w_r){// left side is heavierw_l-=histogram[i_s++];if(((i_s+i_e)/2)>=i_m){w_l+=histogram[i_m+1];w_r-=histogram[i_m+1];i_m++;}}}returni_m;}

The following, is a possible implementation in the Python language:

importnumpyasnpdefbalanced_histogram_thresholding(histogram,minimum_bin_count:int=5)->int:"""    Determines an optimal threshold by balancing the histogram of an image,     focusing on significant histogram bins to segment the image into two parts.    This function iterates through the histogram to find a threshold that divides     the histogram into two parts with a balanced sum of bin counts on each side.     It effectively segments the image into foreground and background based on this threshold.     The algorithm ignores bins with counts below a specified minimum, ensuring that     noise or very low-frequency bins do not affect the thresholding process.    Args:        histogram (np.ndarray): The histogram of the image as a 1D numpy array,                                 where each element represents the count of pixels                                 at a specific intensity level.        minimum_bin_count (int): Minimum count for a bin to be considered in the                                  thresholding process. Bins with counts below this                                  value are ignored, reducing the effect of noise.    Returns:        int: The calculated threshold value. This value represents the intensity level              (i.e. the index of the input histogram) that best separates the significant             parts of the histogram into two groups, which can be interpreted as foreground             and background.              If the function returns -1, it indicates that the algorithm was unable to find              a suitable threshold within the constraints (e.g., all bins are below the              minimum_bin_count).    """start_index=0whilehistogram[start_index]<minimum_bin_countandstart_index<len(histogram)-1:start_index+=1end_index=len(histogram)-1whilehistogram[end_index]<minimum_bin_countandend_index>0:end_index-=1ifstart_index>=end_index:return-1# Indicates an error or non-applicabilitythreshold=(start_index+end_index)//2whileTrue:weight_left=np.sum(histogram[start_index:threshold])weight_right=np.sum(histogram[threshold:end_index+1])ifweight_left>weight_right:end_index=threshold-1else:start_index=threshold+1new_threshold=(start_index+end_index)//2ifnew_threshold==threshold:breakelse:threshold=new_thresholdreturnthreshold

Related Research Articles

A histogram is a visual representation of the distribution of numeric data. The term was first introduced by Karl Pearson. To construct a histogram, the first step is to "bin" the range of values— divide the entire range of values into a series of intervals—and then count how many values fall into each interval. The bins are usually specified as consecutive, non-overlapping intervals of a variable. The bins (intervals) must be adjacent and are often of equal size.

<span class="mw-page-title-main">NumPy</span> Python library for numerical programming

NumPy is a library for the Python programming language, adding support for large, multi-dimensional arrays and matrices, along with a large collection of high-level mathematical functions to operate on these arrays. The predecessor of NumPy, Numeric, was originally created by Jim Hugunin with contributions from several other developers. In 2005, Travis Oliphant created NumPy by incorporating features of the competing Numarray into Numeric, with extensive modifications. NumPy is open-source software and has many contributors. NumPy is a NumFOCUS fiscally sponsored project.

In image processing and photography, a color histogram is a representation of the distribution of colors in an image. For digital images, a color histogram represents the number of pixels that have colors in each of a fixed list of color ranges, that span the image's color space, the set of all possible colors.

<span class="mw-page-title-main">Canny edge detector</span> Image edge detection algorithm

The Canny edge detector is an edge detection operator that uses a multi-stage algorithm to detect a wide range of edges in images. It was developed by John F. Canny in 1986. Canny also produced a computational theory of edge detection explaining why the technique works.

<span class="mw-page-title-main">Fractal flame</span>

Fractal flames are a member of the iterated function system class of fractals created by Scott Draves in 1992. Draves' open-source code was later ported into Adobe After Effects graphics software and translated into the Apophysis fractal flame editor.

<span class="mw-page-title-main">Image segmentation</span> Partitioning a digital image into segments

In digital image processing and computer vision, image segmentation is the process of partitioning a digital image into multiple image segments, also known as image regions or image objects. The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze. Image segmentation is typically used to locate objects and boundaries in images. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain characteristics.

Random sample consensus (RANSAC) is an iterative method to estimate parameters of a mathematical model from a set of observed data that contains outliers, when outliers are to be accorded no influence on the values of the estimates. Therefore, it also can be interpreted as an outlier detection method. It is a non-deterministic algorithm in the sense that it produces a reasonable result only with a certain probability, with this probability increasing as more iterations are allowed. The algorithm was first published by Fischler and Bolles at SRI International in 1981. They used RANSAC to solve the Location Determination Problem (LDP), where the goal is to determine the points in the space that project onto an image into a set of landmarks with known locations.

In numerical linear algebra, the Arnoldi iteration is an eigenvalue algorithm and an important example of an iterative method. Arnoldi finds an approximation to the eigenvalues and eigenvectors of general matrices by constructing an orthonormal basis of the Krylov subspace, which makes it particularly useful when dealing with large sparse matrices.

<span class="mw-page-title-main">Rope (data structure)</span> Data structure for storing strings

In computer programming, a rope, or cord, is a data structure composed of smaller strings that is used to efficiently store and manipulate a very long string. For example, a text editing program may use a rope to represent the text being edited, so that operations such as insertion, deletion, and random access can be done efficiently.

The scale-invariant feature transform (SIFT) is a computer vision algorithm to detect, describe, and match local features in images, invented by David Lowe in 1999. Applications include object recognition, robotic mapping and navigation, image stitching, 3D modeling, gesture recognition, video tracking, individual identification of wildlife and match moving.

<span class="mw-page-title-main">Thresholding (image processing)</span> Image segmentation algorithm

In digital image processing, thresholding is the simplest method of segmenting images. From a grayscale image, thresholding can be used to create binary images.

<span class="mw-page-title-main">Otsu's method</span> In computer vision and image processing

In computer vision and image processing, Otsu's method, named after Nobuyuki Otsu, is used to perform automatic image thresholding. In the simplest form, the algorithm returns a single intensity threshold that separate pixels into two classes, foreground and background. This threshold is determined by minimizing intra-class intensity variance, or equivalently, by maximizing inter-class variance. Otsu's method is a one-dimensional discrete analogue of Fisher's Discriminant Analysis, is related to Jenks optimization method, and is equivalent to a globally optimal k-means performed on the intensity histogram. The extension to multi-level thresholding was described in the original paper, and computationally efficient implementations have since been proposed.

The stationary wavelet transform (SWT) is a wavelet transform algorithm designed to overcome the lack of translation-invariance of the discrete wavelet transform (DWT). Translation-invariance is achieved by removing the downsamplers and upsamplers in the DWT and upsampling the filter coefficients by a factor of in the th level of the algorithm. The SWT is an inherently redundant scheme as the output of each level of SWT contains the same number of samples as the input – so for a decomposition of N levels there is a redundancy of N in the wavelet coefficients. This algorithm is more famously known as "algorithme à trous" in French which refers to inserting zeros in the filters. It was introduced by Holschneider et al.

In robust statistics, Peirce's criterion is a rule for eliminating outliers from data sets, which was devised by Benjamin Peirce.

<span class="mw-page-title-main">Histogram equalization</span> Method in image processing of contrast adjustment using the images histogram

Histogram equalization is a method in image processing of contrast adjustment using the image's histogram.

Connected-component labeling (CCL), connected-component analysis (CCA), blob extraction, region labeling, blob discovery, or region extraction is an algorithmic application of graph theory, where subsets of connected components are uniquely labeled based on a given heuristic. Connected-component labeling is not to be confused with segmentation.

As applied in the field of computer vision, graph cut optimization can be employed to efficiently solve a wide variety of low-level computer vision problems, such as image smoothing, the stereo correspondence problem, image segmentation, object co-segmentation, and many other computer vision problems that can be formulated in terms of energy minimization. Many of these energy minimization problems can be approximated by solving a maximum flow problem in a graph. Under most formulations of such problems in computer vision, the minimum energy solution corresponds to the maximum a posteriori estimate of a solution. Although many computer vision algorithms involve cutting a graph, the term "graph cuts" is applied specifically to those models which employ a max-flow/min-cut optimization.

In computer science, the earth mover's distance (EMD) is a measure of dissimilarity between two frequency distributions, densities, or measures, over a metric space D. Informally, if the distributions are interpreted as two different ways of piling up earth (dirt) over D, the EMD captures the minimum cost of building the smaller pile using dirt taken from the larger, where cost is defined as the amount of dirt moved multiplied by the distance over which it is moved.

Color normalization is a topic in computer vision concerned with artificial color vision and object recognition. In general, the distribution of color values in an image depends on the illumination, which may vary depending on lighting conditions, cameras, and other factors. Color normalization allows for object recognition techniques based on color to compensate for these variations.

<span class="mw-page-title-main">Circular thresholding</span> Algorithm in image processing

Circular thresholding is an algorithm for automatic image threshold selection in image processing. Most threshold selection algorithms assume that the values lie on a linear scale. However, some quantities such as hue and orientation are a circular quantity, and therefore require circular thresholding algorithms. The example shows that the standard linear version of Otsu's method when applied to the hue channel of an image of blood cells fails to correctly segment the large white blood cells (leukocytes). In contrast the white blood cells are correctly segmented by the circular version of Otsu's method.

References

  1. A. Anjos and H. Shahbazkia. Bi-Level Image Thresholding - A Fast Method. BIOSIGNALS 2008. Vol:2. P:70-76.
  2. Nobuyuki Otsu (1979). "A threshold selection method from gray-level histograms". IEEE Trans. Sys., Man., Cyber. 9: 62–66.
  3. Ridler TW, Calvard S. (1978) Picture thresholding using an iterative selection method, IEEE Trans. System, Man and Cybernetics, SMC-8: 630-632.