RU2311680C1 - Method for automated division of pixels of raster images onto brightness level groups on basis of repeat values thereof - Google Patents

Abstract

FIELD: recognition of raster images, possible use for determining efficiency of determining of threshold values of brightness of pixels or characteristics, derived from these for given matrices of raster images.

SUBSTANCE: for given raster image, which has a row of pixel brightness levels, having repeat values and common volume, group division is introduced for groups of successive brightness levels, where as group quality characteristic, inertia momentum of repeat values is taken relatively to group median, for which totals of repeat values on left and right are equal. Given criterion makes it possible to efficiently select both optimal number N of groups in a bar chart, and also composition of groups in cases when nature of bar chart allows it.

EFFECT: increased efficiency when determining threshold values of brightness of pixels.

3 dwg

Description

The invention relates to the recognition of raster images and is intended to increase the efficiency of determining threshold brightness values of pixels or characteristics derived from them for a given matrix of raster images. The threshold methods use the fact that the pixels that form the images of individual image objects have similar brightness levels and they occupy rather large sections of the total image area. Therefore, the decision when assigning a pixel to a particular image object can be made based on a comparison of the analysis of its brightness with a certain threshold value.

Recognition systems are known, for example, when scanning images in which thresholds are set manually, for example, in EPSON scanning systems [1]. These methods require the mandatory participation of a person in a preliminary image analysis and are not applicable in automatic recognition systems.

Closest to the totality of features is the method of splitting into groups (the criterion of collapse into heaps), proposed in [2]. Here we consider some numerical characteristic s, which can take n different values of s _i (i = 1, ..., n) having repeatability values specified by the histogram Н = {h ₁ , ..., h _n }. The total number of numbers is determined

При помощи порогов совокупность чисел s разбита на кучи {s¹,...,s^N} из подряд стоящих значений чисел. Для каждой кучи s^u рассмотрен объем Q^u и дисперсия σ^u2. Показатель кучности задан формулойand its dispersion

Using thresholds, the set of numbers s is divided into heaps {s ¹ , ..., s ^N } from consecutive values of numbers. For each heap s ^u, the volume Q ^u and the variance σ ^{u2 are considered} . The accuracy indicator is given by the formula

A partition with the lowest value of the exponent κ is taken as the best. In the absence of restrictions for any histogram H, the global minimum of the indicator κ = 0 will be achieved on a trivial heaping, in which each heap consists of only one number s _i . However, such a global minimum does not provide constructive information on image separation. Therefore, it was proposed to impose additional restrictions on the search area: 1) at the beginning of the group s ^u _n , the repeatability values increase, and at the end s ^u _к , they decrease, 2) the volume of each heap should not be too small (Q ^u / Q≥1 / 8 ), 3) the number of heaps should not be more than 4 (N≤4).

The proposed method has the following disadvantages.

1. With increasing N, the value of the criterion κ usually also increases. This does not allow us to compare threshold partitions with different values of N. This criterion allows us to compare partitions with the same number of groups N.

2. At the same time, for the model histogram of the type shown in FIG. 1, the criterion κ without introducing a threshold (N = 1) and with the introduction of one threshold (N = 2), giving the desired separation, is zero. Those. the considered criterion does not always allow comparing partitions with the same number of thresholds.

The objective of the invention is to provide a method for automatically dividing into groups of brightness levels of pixels of raster images according to their repeatability, which will not have the above disadvantages.

The problem is achieved by the fact that the proposed method of automated splitting into groups of brightness levels of pixels of raster images according to their repeatability values, namely, for a given raster image, which has a number of brightness levels of pixels having repeatability values and total volume, a division into groups of consecutive brightness levels, and at the beginning of the group there is an increase in repeatability values, and in the end - their decrease, the ratio of the volume of each group to the total volume should be not less than 1/8 and the number of groups should not be more than 4, a quality indicator is introduced for each group, and a generalized quality indicator is introduced for the entire partition, the optimality criterion of which is the minimum, according to the invention, the moment of inertia of the repeatability values relative to the median is taken as the group quality indicator groups, for which the sums of repeats on the left and on the right are equal to each other, and a generalized quality indicator of the whole partition into groups has the form:

where N is the number of groups

- объем группы с номером u (u=1, ..., N),

- the volume of the group with the number u (u = 1, ..., N),

{h ₁ , ..., h _n } - repeatability corresponding to pixel brightness levels {s ₁ , ..., s _n },

- показатель качества группы с номером u,

- quality index of the group with number u,

s ^u _n , s ^u _k - the initial and final brightness values in the group with number u,

s ^u _m is the median of the brightness values in the group with number u.

Consider for n brightness levels of pixels s _i (i = 1, ..., n) a histogram of their repeatability Н = {h ₁ , ..., h _n }. As experiments have shown, for a fixed group s ^{u, a} particular quality criterion that best reflects the “accuracy” property is not dispersion, but the moment of inertia of the group relative to its median s ^u _m :

In order to combine the selected particular criteria into one general, we consider as a model a uniform distribution of the intensity characteristic h with a large number of values uniformly distributed in the interval [0,1] (Figure 2). In this histogram, the criterion should not highlight thresholds, since in reality they do not exist.

In the absence of dividing the histogram into groups, the total moment of inertia relative to the median is

where Q = h · 1 is the total volume of the histogram.

With an arbitrary partitioning of this histogram into N groups, which along the s axis occupy segments of length s ₁ , s ₂ , ..., s _N (s ₁ + s ₂ + ... + s _N = 1), their moments of inertia will be equal to

The value of the total total criterion will remain unchanged (before and after the partition) in the case when each particular criterion f (g ^u ) will be included in the total amount with a weight coefficient of 1 / (s _u ² ).

Introducing the values of the volumes of groups q ^u instead of s _u in the coefficients in the considered problems, we obtain a generalized criterion of the following form:

This criterion makes it possible to efficiently isolate both the optimal number N of groups in the histogram and the composition of the groups in those cases when the nature of the histogram allows this.

For the practical implementation of the proposed method, the following algorithm can be used.

INITIAL DATA.

For some numerical characteristic s, a histogram H is given, as well as a threshold value δ of an extremely small relative volume of groups. It is necessary to find out the possibility of threshold separation of the histogram for a given histogram. If possible, then find the number N of groups in the histogram and their composition at which the generalized criterion reaches a minimum, provided that the relative volume of the groups does not exceed δ and the groups are separated in the region of local minima in the histogram.

PRELIMINARY ACTIONS.

The total volume of the histogram Q and the threshold extremely small value of the volume of the group Q _pr = δ · Q are calculated.

Since the separation should occur in the region of local minima in the histogram, the algorithm starts with their search.

STEP 1. Preview the histogram. Allocation of all local minima on it. These minima are single (when the condition h _{S (i-1)} > h _{S i} <h _{S (i + 1)} is satisfied at the minimum point s = s _i ) and group, when several consecutive histogram values take the minimum value. In both cases, it becomes necessary to set a threshold value with respect to the minimum values. Since the value of the criterion is less when the composition of the groups is more uniform in the value of h _S , the minima are added to those intermediate groups of values with a closer average value. As a result, a linear array of possible thresholds P of a certain length n _{m is created} . If there are no local minima in the histogram, then it is considered to be inseparable into groups. Exit the algorithm with a negative answer.

STEP 2. Calculation of the initial value of the criterion in the absence of thresholds: F _beg = F (N = 1). We assign the same value to the current minimum value of the criterion: F _min = F _beg .

STEP 3. Enumeration of all possible threshold options, calculation of criterion values for them, and selection of the best option.

(один вариант, в котором в набор не вошел ни один порог, рассмотрен на ШАГЕ 2). Кодируя каждый из вариантов числом от 1 до

, вхождение каждого из порогов в выбранном варианте i находим, разлагая это число в двоичной системе в вектор длины n_m. Те позиции j, на которых стоит 1, задают вхождение j-го порога в набор. Если стоит 0, то порог не входит в набор.3.1. Possible threshold generation. Since for each possible threshold P _i there are two possibilities - to enter the set or not, the total number of unexamined threshold options is

(one option in which not a single threshold is included in the set is considered in STEP 2). Encoding each of the options from 1 to

, we find the occurrence of each of the thresholds in the selected option i by expanding this number in the binary system into a vector of length n _m . Those positions j, at which stands 1, determine the occurrence of the jth threshold in the set. If it is 0, then the threshold is not included in the set.

3.2. Checking a set of thresholds for an extremely small volume of the group Q _pr Each specific set of thresholds on the histogram sets a certain set of groups. The volumes of all groups Q ^u are checked for the condition Q ^u > Q, _etc. If at least one of the groups does not meet the condition, the entire set is excluded from further analysis.

3.3. Criterion Calculation. Checking the optimality of threshold thresholds. For the selected set of groups s ¹ , s ² , ..., s ^N , the value of the criterion F (s ¹ , s ² , ..., s ^N ) is calculated. If the condition F (s ¹ , s ² , ..., s ^N ) <F _min is satisfied, then a more optimal partition into groups is found. In this case, we perform the assignment F _min = F (s ¹ , s ² , ..., s ^N ) and remember the corresponding threshold separation.

STEP 4. Final check. If, after completing the exhaustive search of all threshold options, it turned out that F _min = F _beg , this indicates that the histogram is poorly separable into groups and the introduction of thresholds on it is impractical. Exit the algorithm with a negative answer.

If F _min <F _nach , then we obtain the desired optimal number of groups N and a partition of the set of values into groups {s}.

Example.

INITIAL DATA. For a two-color bitmap 16-color image (n = 16) of size 20 × 80, the histogram obtained in FIG. 3 is obtained, in which

h ₀ = 14; h ₁ = 9; h ₂ = 9; h ₃ = 14; h ₄ = 13; h ₅ = 8; h ₆ = 11; h ₇ = 9; h ₈ = 12; h ₉ = 7; h ₁₀ = 7; h ₁₁ = 7; h ₁₂ = 10; h ₁₃ = 8; h ₁₄ = 10; h ₁₅ = 12.

The threshold value of the extremely small relative volume of the groups is δ = 0.15.

It is necessary to find out the possibility of threshold separation of the histogram for a given histogram. If possible, then find the number N of groups in the histogram and their composition at which the generalized criterion reaches a minimum, provided that the relative volume of the groups does not exceed δ and the groups are separated in the region of local minima in the histogram.

PRELIMINARY ACTIONS.

The following is calculated: 1) the total histogram volume: Q = 160, 2) the threshold extremely small value of the group volume Q _pr = δ · Q = 0.15 · 160 = 24.

STEP 1. The internal local minimums of the histogram are selected, which specify the beginning of the possible groups: 1, 6, 9, 13. Their total number is 4.

STEP 2. The initial value of the criterion in the absence of thresholds: F _beg = F (N = 1) = 0.141392. We assign the same value to the current minimum value of the criterion: F _min = F _beg .

STEP 3. Enumeration of all possible threshold options, calculation of criterion values for them, and selection of the best option.

Option 1000, the value of the criterion: F = 0.146384> F _min .

Option 0100, the value of the criterion: F = 0.144421> F _min .

Option 1100, the value of the criterion: F = 0.14888> F _min .

Option 0010, the value of the criterion: F = 0.131995 <F _min , F _min = 0.131995.

Option 1010, the value of the criterion: F = 0.134505> F _min .

Option 0110, the value of the criterion: F = 0.128107 <F _min , F _min = 0.128107.

Option 0001, the value of the criterion: F = 0.133057> F _min .

Option 1001, the value of the criterion: F = 0.132206> F _min .

Option 0101, the value of the criterion: F = 0.140083> F _min .

Option 1101, the value of the criterion: F = 0.144533> F _min .

Variants 0011, 1011, 0111, 1111 have groups with a volume less than Q _pr , so they are not analyzed.

As a result, option 0110 with the criterion value F = 0.128107 was adopted as the optimal one. The threshold values are 5.5 and 11.5. Moreover, N = 3, s ¹ = {0,1,2,3,4,5}, s ² = {6,7,8,9,10,11}, s ³ = {12,13,14, fifteen}.

Claims (1)

A method for automatically splitting into groups of brightness levels of pixels of raster images according to their repeatability values, namely, for a given raster image that has a number of brightness levels of pixels having repeatability values and total volume, a division into groups of consecutive brightness levels is introduced, moreover at the beginning of the group there is an increase in the repeatability values, and in the end - their decrease, the ratio of the volume of each group to the total volume should be at least 1/8 and the number of groups should not be more than 4, for a quality indicator is introduced for each group, and for the entire partition, a generalized quality indicator, the optimality criterion of which is the minimum, characterized in that the moment of inertia of the repeatability values relative to the median of the group for which the sums of repeatings on the left and right are equal to each other is taken as an indicator of the quality of the group, and a generalized indicator of the quality of the entire grouping has the form:

where N is the number of groups of pixel brightness levels, s ¹ , s ² , ..., s ^N , are groups of pixel brightness levels,

- the volume of the group with the number u (u = 1, ..., N), {h ₁ , ..., h _n } - repeatability corresponding to pixel brightness levels {s ₁ , ..., s _n },

- quality index of the group with number u, s ^u _n , s ^u _k - the initial and final brightness values in the group with number u, s ^u _m is the median of the brightness values in the group with number u.

Images