A new segmentation method of signals distorted by noise is discussed. Unlike other known methods, for example, the Canny method, a priori data on interference and / or a signal (image) is not used. Segmentation of signals and halftone images distorted by interference is one of the oldest problems in computer vision. But human vision solves this task almost independently of our consciousness. It was discovered for visual neurons, that sizes of receptive fields' excitatory zones change during visual act, which eventually mean dynamical changes in visual system's resolution i.e. coarse-to-fine phenomenon in living organism. We assumed that "coarse-to-fine" phenomenon, i.e. several different resolutions, is used in human vision to segment images. A "coarse-to-fine" algorithm for segmentation of experimental graphs was developed. The main difference of algorithm mentioned above from others is that decision is made taking into account all partial solutions for all resolutions being used. This ensures stability of final global solution. The algorithm verification results are presented. It is expected that the method can naturally be expanded to segmentation of halftone images.
Experimental curves represent the results of measurements, as a rule, distorted by interference. The most basic feature of the experimental curve is its shape, which displays function that generates the observed realization of curve and characterizes parameters of the displayed object or process. It is assumed that the measured values are represented the realization of some unknown function existing on a given measurement interval, and the result of the measurement is a finite sequence of pairs "reference number-value". Since different curves that relate to the same object can differ from each other in scale, interference level, number of measurements, etc., direct use of neural network methods or methods that rest on statistical pattern recognition for solving the problem of comparing the shape of graphs or curves does not seem possible. In this case, the unknown functions that describe experimental curves must be approximated by functions that are invariant to affine transformations for their subsequent processing and comparison.
Since images, as well as signals, can be considered as experimental realizations of some unknown functions, some image processing methods can be used in signal processing, in particular, the variable resolution method. The aim of our research is to introduce new methods for processing signals and images, in particular, to develop a new algorithm for segmenting experimental curves suitable for automated signal processing based on these methods and finally, to demonstrate the results of this algorithm's application to one-dimensional signals distorted by interference.
In 70s of the last century, neurophysiologists discovered the phenomenon of changes in sizes of
receptive fields’ excitatory zones in the visual system neurons, which was investigated and confirmed
later [
To analyze continuity of a function in continuous two-dimensional space, the classical definition of continuity of a function in e-d form is successfully used: if for each e>0 there exists such d>0 that for any value of variable x that belongs to δ-neighborhood of point c the values of function f(x) belong to e-neighborhood of f(c). You should pay attention to how the continuity of function is checked at a point. Starting with a certain value |x1-c|, the neighborhood of the point c decreases (|x1−c|>|x2−c|, |x2−c|>|x3−c|, ...) tending to 0. Here f(x) is assumed to be continuous at a point c if the neighborhood f(c) also tends to 0 (|f(x1)-f(c)|>|f(x2)-f(c)|, |f(x2)-f(c)|>|f(x3)-f(c)|, ...). Thereby, to analyze the continuity of a function at a point, changing neighborhood of this point is used.
The decrease in the size of receptive field excitatory zone can be considered as a decrease in proportions of point neighborhood at center of the receptive field. The process, which is used in the analysis of continuity of a function at a point in classical mathematical analysis, is repeated in visual system of human and animals each visual act. The essential difference between resolution changes in visual system from analysis of continuity of a function at a point is that the elements of the receptive field are objects of a discrete space. Similarly, the classical definition is unsuitable for analyzing continuity of experimental curves, since they are representations of unknown functions and are identified as sequences of values, which in turn are sets of points in some discrete space. However, at the initial moments of visual act, the excitatory zones of neurons contain many points (receptors) and until the receptor sets in the excitatory zones of the receptive fields are not empty, the definition of continuity can be applied to the brightness function determined in the discrete space of receptors and it does not contradict to classical theory of discontinuity. Thus, the above phenomenon of resolution changes in human visual system can be used to create new method of signal processing based on the concept of variable resolution.
The idea to consider initial data with variable resolution is used by researchers and developers spontaneously, most often to effectively solve problems of large computational complexity that arise when processing the visual representation of signals. Such an approach makes it possible to exclude inappropriate objects or non-informative signal sections at the early stages of processing and apply the computationally-intensive part of algorithm to reduced volume of data. The review of methods from the field of image processing that use the idea of variable resolution to save computational resources is presented. The original image is considered with several reduced resolutions in each of them.
An example is given in [
If you try to apply structural recognition methods to the images in Figure 1c, 1d the same results will be obtained as for Figure 1b: the contours of the grid cells will be defined. This statement was verified using the well-known text recognition program FineReader. The text in Figure 1a was successfully recognized. The result of processing images on Figure 1b, 1c, 1d is a refusal to recognize the object in the image due to the inability to locate it. When the resolution of these images is reduced several times, the resulting images (Figure 2) are recognized satisfactorily because the recognition program does not detect the grid lines. This example demonstrates the importance of choosing the right resolution when processing an image, or, if this is not possible, using a variable resolution. where G( ) - Gaussian filter for the value of the standard deviation ,
g (i, j) - is an element of the "blurred" image.
In the automated processing of noisy images, preliminary processing of the input image using different filters is used to eliminate undesirable details.
The very first case of image processing using variable resolution in order to eliminate unwanted
details is an integral part of the widely used [
Partial values of the gradients for the horizontal gi (i, j) and vertical g j (i, j) directions in the blurred image g (i, j) , using, for example, the Sobel operator to obtain the value of the total gradient M (i, j) and its direction (i, j) as are calculated.
The values of M (i, j) , using the threshold T, which should be chosen so that all contour elements are selected, while most of the interference is eliminated, are obtained MT (i, j) :
M (i, j) gi2 (i, j) g 2j (i, j)
g j (i, j) (i, j) arctg
gi (i, j) M (i, j), if MT (i, j) 0, otherwise
M (i, j) T
To improve the quality of the method, two thresholds are used T1 and T2, where T1 < T2. If a pixel v(i,j) with a value T1 < MT (i, j) <T2 has two neighboring pixels in the gradient direction (i, j) , for each of which T1 < MT (i, j) < T2, its value as a contour element is saved, and if not, it is equated to 0. All non-zero elements are combined to create a closed contour of the object, using a special algorithm. In the Canny method, the variable resolution is used implicitly, since the operator selects the degree of blurring , but this is done based on his subjective considerations of the nature of the interference. Disadvantages of the Canny method:
object boundaries in the form of pixel sequences are the result of the algorithm, but a pixel is a two-dimensional entity, while an object boundary is usually represented as a line, in particular, a broken line without thickness;
the result of the Canny algorithm depends on the variable parameter of the Gaussian filter - , which has the value of the standard deviation of the normal probability distribution law (Figure 3).
The result of its work depends on the unknown parameter σ - "blur", which has the meaning of dispersion. In general, if you use a filter to preprocess a noisy image, the result will depend on the size of the filter aperture.
σ=1 σ=1.7 σ=4
Resolution reduction is widely used to reduce the computational complexity and improve the
performance of existing image processing and recognition algorithms. For example, in [
The algorithm discussed in [
The task of establishing a correspondence between the pixels of two images of human faces
(finding a markup) [
Dynamic programming is often used in tasks such as speech recognition, character recognition,
pattern matching for deformable objects, and road tracking. However, such tasks often lead to state
spaces of enormous size, which can make calculations unfeasible, even with the use of dynamic
programming. To overcome such obstacles, it is proposed in [
The purpose of using variable-resolution methods in the cases discussed above is to identify parts
of the original image or parts of the original dataset that contain information that seems useful for
solving the problem at hand. Complex calculations are performed only on these parts. At the same
time, the nature of the resolution change mechanism used in each case is not important. It should be
noted that a large number of image recognition tasks that have NP-complexity or cannot be solved
using traditional methods are solved instantly in the human visual system, and tasks related to video
processing are solved in real time. Therefore, it would be natural to turn to the results of studying the
processes in the human visual system obtained in neurophysiology to create new methods and
algorithms for processing visual information. In previous years, researchers have already tried to
move forward in this direction, using the results of vision neurophysiology that were relevant at the
time. For example, stimulus direction-sensitive cells in the primate visual system show a certain range
of spatial sizes, in particular, if the size of receptive fields is compared between different cortical
areas, such as primary visual cortex and the middle temporal lobe [
According to the authors, this is important given the large number of iterations required by
relaxation algorithms and the surprising speed with which humans can reliably estimate the speed of
motion. Based on this approach, a two-level multiscale adaptive neural network model for calculating
motion parameters in the middle part of the temporal lobe of primates was presented in [
Statement of the problem: there exists an unknown function y = f(x) with domain bounded to [a, b]. The image of this function is observed on [a, b]. The resolution needed for analyzing the image of this function is unknown. Under the assumption that the given image of a function represents an unknown piecewise smooth function, the boundaries of partial segments a = t0 < t1 <…< tN = b and their number N+1 should be found. Analytical solution of the segmentation problem stated above should be considered as finding the points of discontinuity for unknown piecewise smooth function. The following discontinuities are of interest: jump discontinuities, when the -neighborhood of the function is empty in a given point and removable discontinuities when the first order derivative of function does not exist in the given point (jump discontinuity of function gradient). However only the image of unknown piecewise smooth function is observed so we are allowed to consider only the discrete analog of discontinuities in the form of irregular points on experimental curve.
Preliminary stage consists of presenting the experimental data as I “reference-value” pairs {i, xi};
i = 1, 2 … I, that corresponds to maximum resolution. Acquisition of coarse resolution signal is
performed (as well as in visual system) using a source signal with maximum resolution. Partial
answers of segmentation are considered as the set of breaking points found on each resolution. The
result of segmentation is considered as sequence of breaking points from the finest resolution being
taken from the longest sublist of partial answers with the same set of breaking points. Further details
of the algorithm are described in [
The algorithm for segmenting an experimental curve using variable resolution has been implemented as a computer program in Matlab 2010b environment (Figure 4). Figure 4 a.1, b.1 shows the numbers of samples of the experimental curve along the abscissa axis and the number of resolutions at which the experimental curve is investigated on the ordinate axis. The segments in Figure 4 a.1, b.1 correspond to the intervals in the region of the exact samples on which discontinuities in the continuity of the experimental curve are found. Figure 4 b.1 shows that information on the available jumps in the experimental curve obtained at low resolutions makes it possible to exclude from consideration regions at maximum resolution in which jumps are detected due to the presence of noise. 5.2.
With minor additions, the algorithm was also used in the cardiac signal segmentation application. It was tested during two-part experiment: on cardiac signals obtained during state of rest and during special patient activity. While in the first case the signal was obtained from patients the conditions under which this experiment was conducted where almost ideal. The distortions in the signal weren’t related to R-peak form. So the goal in this case was only to approve the ability of implemented algorithm to find R-peaks in the cardiac signal distorted by noise. The algorithm was successfully tested on over 100 samples. The results of segmentation for the 90-second cardiac signal are shown in
39 cardiograms that were obtained during hypoxic probes from four patients were considered. Hypoxic probes were used to assess the functional state of a person. They consisted of several stages where the person should breathe calmly, make deep breathes and hold breath for a certain period of time. All that activities modulate the heart activity and lead to changes in time intervals between sequential R-peaks and in amplitude of R-peaks (Figure 6).
Cardiograms were obtained using mobile cardiac signal registrator from Solvaig company [
In order to increase the accuracy of algorithm under consideration its parameters were fine-tuned. The length of sliding window was selected to contain at least two QRS-complexes. The overlapping of two neighboring windows was picked so that it wasn’t less than the length of QRS-complex in order to exclude possible missing of R-peak due to incomplete placement of significant signal part in current window under consideration. Oracul and Cardiolyse applied noise filtering as the first step of signal processing. The algorithm under consideration used the cardiac signal “as is” without any preprocessing and without any apriori information about noise parameters. Cardiogram annotations from each program where converted to one unified markup file format having only timestamps, numbers of samples from start, QRS-complex type and R-peak amplitude (Figure 7). The number of R-peaks found by reference programs where compared to that number from algorithm under consideration and the number of identically segmented cardiograms were calculated.
A
j
In order to obtain the annotation files cardiograms were processed by each program respectively. Resulting files were placed in the folders near the initial file. The average time to obtain the annotation file for Oracul was 4 seconds. Since cardiograms for processing were sent to Cardiolyse with POST-query and the annotation returned in the response to subsequent GET-query the average processing time was not calculated. For the program that implements algorithm under consideration the average time to process cardiogram and write down the markup file was 0.98 seconds. During the segmentation results comparison it turned out that due to Oracul and Cardiolyse medical diagnostic orientation they add only the result of segmentation for full cardiac cycles. Furthermore Oracul could skip several visually normal QRS-complexes at the beginning and at the end of cardiogram. At the same time the algorithm under consideration searched for R-peaks using pattern and without further cardiac cycle analysis. Thus the generated markup with algorithm under consideration could have several R-peaks from incomplete cardiac cycles at the beginning and at the end of cardiogram and that result was considered valid. Another limitation of implemented algorithm due to its “non-diagnostic” orientation was revealed. Both Oracul and Cardiolyse marked QRS-complexes with one of four types. N for normal QRS-complexes, Q, V, S – QRS-complexes with some deviation from normal but still having useful information. QRS-complexes with deviations also got to annotation files but their form could be substantially different from normal (Figure 8) so the implemented algorithm failed to find them. 0:00:00.100 0:00:00.946 0:00:01.792 0:00:02.610 0:00:03.412 0:00:04.256
Taking into account everything aforementioned the following results were obtained (Table 1). As we can see the distorted R-peaks that were found by reference algorithms and were skipped by the implemented algorithm are only 2 % from their total amount. Nevertheless they were found in almost every second cardiogram. That didn’t allow obtaining a value of identically segmented cardiograms in “referenced algorithm – implemented algorithm” pairs more than 60 percent.
The example of cardiogram primary segmentation with implemented algorithm is presented on Figure 9. The abscissa axis has the samples’ numbers and the ordinate axis shows the amplitude of signal in millivolts. Rhythmograms and amplitudeograms that were built from the result of segmentation with each algorithm are presented on Figure 10. On Figure 10 for rhythmograms the abscissa axes shows interval numbers between R-peaks, the ordinate axis shows the length of these intervals in seconds. For amplitudeograms the abscissa axes shows the R-peak numbers, the ordinate axis shows the amplitude of the corresponding R-peak in millivolts. As long as Oracul and Cardiolyse provide the information on amplitudes of R-peaks for filtered signal the amplitudeograms (b) and (c) also contains amplitudeograms based on signal after filtering denoted in red line. The differences in amplitudeograms on (b) and (c) presumably are due to different filter settings in each system. We can make an assumption that filter used in Cardiolyse remove more significant information resulting in distortion of some QRS-complexes like on Figure 8. Due to that fact the amplitude of S-peak is placed into annotation file instead of R-peak. Also due to “diagnostic” orientation of reference algorithms the rhythmograms on Figure 10.b, 10.c contain an extra point near interval number 150. That means that cardiogram has the sample resembling distorted R-peak. The implemented algorithm skips that sample.
Thus, the segmentation of the experimental curve can be carried out as a search for the points of discontinuity of the piecewise smooth function that generates it. It is possible to construct new methods for segmenting experimental curves using the concept of variable resolution based on the classical theory of continuity of functions and actual advances in the field of neurophysiology of vision. In the algorithm under consideration processing results for all used resolutions are taken into account when making decision on segmentation. The efficiency of the algorithm is confirmed by the results of processing for signals and graphs distorted by interference. In this case no a priori information about the noise level was used. The experiment on cardiogram segmentation with algorithm being discussed using variable resolution provided satisfactory results compared to reference algorithms. Amplitudeograms and rhythmograms that were built from R-peak markup could be used as initial data in further research work involving heart rate variability. These solutions will be used in the development of new methods for processing halftone images as well.