Proceedings of the 27th International Symposium Nuclear Electronics and Computing (NEC’2019) Budva, Becici, Montenegro, September 30 – October 4, 2019 AN INTERVAL-VALUED IMAGE BASED APPROACH TO DETECT EDGES IN AERIAL IMAGES A. Nechaevskiy1 , A. Elaraby2,a 1 Joint Institute for Nuclear Research, Dubna, Russia 2 Department of Mathematics &Computer Science, Faculty of Science, South Valley University, Egypt E-mail: a.elaraby87@gmail.com The ability to propagate the uncertainty information during image processing can be very important in different applications. Detecting edges are an important pre-processing step in image analysis. Best results of image analysis extremely depend on edge detection. Edge detectors are intended to detect and localize the boundaries or silhouettes of objects appearing in images. Up to now many edge detection methods have been developed. But it may have some weaknesses in correct detection of the scope of complications for aerial images or medical images, because of the high variation rate in these images. This paper introduces a verification framework to detect edges based on interval techniques using measuring diversity of pixel’s intensity and randomness of intensity distribution within the framework of information theory. Keywords: Image analysis, Interval arithmetic, Information theory, Edge detection; Remote sensing images Andrey Nechaevskiy, Ahmed Elaraby Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 266 Proceedings of the 27th International Symposium Nuclear Electronics and Computing (NEC’2019) Budva, Becici, Montenegro, September 30 – October 4, 2019 1. Introduction In image processing tasks, there are various sources of ambiguity and uncertainty to be considered when performing the processing [1]. Images captured situations are not always ideal or stable; this is one of examples of uncertainty regarding the measured pixel values, Also which in some cases is related to the spatial position of an image object or technical limitations. So, in practice we always deal with numerical and spatial approximations of pixel values. To overcome this uncertainty we need suitable image models, which also enables to image processing without losing the information regarding the uncertainty. Since information on the level of uncertainty will influence an expert’s attitude, so the ability to propagate the uncertainty information during image processing tasks can be very important. In order to deal with the uncertainty – in such a manner that it is incorporated in an image model and can be processed together with an image – an image verification framework introduced based on interval arithmetic. Interval arithmetic is a powerful tool to deal with the uncertain data, the concepts of interval arithmetic are discussed in [2-3] and some of the related work in interval arithmetic and interval valued fuzzy set presented in [4-9]. In a grayscale image, the pixel value indicates the amount of white or black existing at that specific position in an image [10-12]. In image processing, most algorithms assumes that the pixel values are certain, although in practice the measured values of pixels might be uncertain and just indicate a likely value of an image at a specific location. The uncertainty of the pixel value is an immediate fact if considered that any tool will round captured values of pixel down or up to the finite set of allowed values. The uncertainty of the pixel value is an immediate fact if considered that any tool will round captured values of pixel down or up to the finite set of allowed values. This might be the issue under identical registration circumstances, and will grow when these circumstances change (e.g., weather conditions); Also, the pixels that belong to an edge of an object might slightly shift position in various takes (e.g., while the camera slightly shifts position), this could result in large differences in the measured value of a specific pixel, and consequently in a large uncertainty of the real value of that pixel, i.e., for that specific spatial position in an image; the process of digitalization, it's naturally a level of uncertainty, as the intensity of gray tones of the pixel in a digital image will never correspond the existent in the nature, as an image refers to a continuous function, denoted by I(x, y), where the value of I(x, y) in the coordinates space gives an image brightness (intensity), the digitalization of value quantification called gray levels and the digitalization of the space coordinates called sampling of an image. So, for these reasons, it's appropriate to compute with grayscale intervals, where the interval represents the set to which the actual grayscale values belongs. Various applications in image processing and bioinformatics may benefit from an image verification model. 2. Proposed Methodology 2.1 Interval-Valued Image The concept of interval analysis is to compute with intervals of real numbers instead of real numbers and it considers a powerful tool to determine the effects of uncertain data [2,13-16]. To overcome the various types of uncertainty and vagueness when doing image processing tasks, as most of those types are contextual, in the sense that they could be present (or not) in an image, based on the situation of an image was captured at., We use a verification interval-valued representation of an image in introduced in [16]. From an image I, we generate the verification interval-valued images IV(L) , IV(U) and IV(M) as following: IV(L) = [𝑚𝑎𝑥(0, I(x,y) −1)] (1) IV(U) = [𝑚𝑖𝑛(255, I(x,y) + 1)] (2) IV(L) +IV(U) IV(M) = [ ] (3) 2 267 Proceedings of the 27th International Symposium Nuclear Electronics and Computing (NEC’2019) Budva, Becici, Montenegro, September 30 – October 4, 2019 That is, we assign to each image position an interval as IV(L) and IV(U) which include all of the brightness values modified by ± 1 tone and IV(M) is the midpoint image of an interval images IV(L) and IV(U) where the brightness values can be modified by α interval operator as 0 < α < 1. So, once we have interval representation images, then we can apply different strategies of computing, as, we can apply the computing strategies individually for IV(L) , IV(U) and IV(M) images or together. Figure 1, includes an example of an image, together with the verification interval-valued representation. Figure 1. Schematic overview of an interval valued model of Aerial image where different steps can be observed. Original image (a) is divided into two parts (Upper bound IV(U) image (b) and lower bound IV(L) image (c)) following the midpoint IV(M) image (d) 2.2 Edge Detection Approach The concept of entropy become increasingly important in image processing, when an image can be interpreted as an information source with the probability law given by its image histogram [17- 18]. Let p1 , p2 , ⋯ ⋯ , pk be the probability distribution of a discrete source. Therefore, 0 ≤ pi ≤ 1, i = 1,2, ⋯ , k and ∑ki=1 pi = 1, where k is the total number of states. The entropy of a discrete source is often obtained from the probability distribution. The Shannon entropy [18] defined as: 𝐻(𝑝) = − ∑𝑘𝑖=1 𝑝𝑖 𝑙𝑛( 𝑝𝑖 ) (4) Shannon entropy has the extensive property (additively) S(X + Y) = S(X) + S(Y). Tsallis [18] has proposed a generalization of the BGS statistics as: 1 Sα = 1−α (1 − ∑zi=1 pαi ), (5) where the real number α is an entropic index that characterizes the degree of non-extensivity. This expression recovers to Shannon entropy in the limit α →1 . Tsallis entropy has a non-extensive property for statistical independent systems, defined as: Sα (X + Y) = Sα (X) +Sα (Y) + (1- α) ∙ Sα (X) ∙ Sα (Y). (6) For an image with k gray-levels, let p1 , p2 , … . , pt , pt+1 , … . , pkbe its probability distribution, where pt is the normalized histogram (i.e.,pt = ht ⁄(M × N)) and ht is the gray level histogram. Using this distribution, we can derive two probability distributions, one for the object (class A) and the other for the background (class B), as follows: 𝑝 𝑝 𝑝 𝑝 𝑝 𝑝 𝑝𝐴 : 𝑃 1 , 𝑃 2 , … . . , 𝑃 𝑡 , 𝑝𝐵 : 𝑃𝑡+1 , 𝑃𝑡+2 , … . . , 𝑃 𝑘 , (7) 𝐴 𝐴 𝐴 𝐵 𝐵 𝐵 𝑃𝐴 = ∑𝑡𝑖=1 𝑝𝑖 , 𝑃𝐵 = ∑𝑘𝑖=𝑡+1 𝑝𝑖 (6) where 𝑡 is the threshold value. The Shannon entropy for each distribution can defined as: 268 Proceedings of the 27th International Symposium Nuclear Electronics and Computing (NEC’2019) Budva, Becici, Montenegro, September 30 – October 4, 2019 t z X (t) Y (t) S = − ∑ pX ln pX , S = − ∑ pY ln pY (7) i=1 i=t+1 Tsallis entropy of order α for each distribution can defined as: t z 1 1 SαX (t) = (1 − ∑ pXα ) , SαY (t) = (1 − ∑ pYα ) (8) α−1 α−1 i=1 i=t+1 Tsallis entropy SαX (t) is parametrically dependent upon the threshold value 𝑡 for the foreground and background. When Sα (t) is maximized, the luminance level 𝑡 that maximizes the function is considered to be the optimum threshold value. 𝑡 ∗ = Arg max [SαX (t) + SαY (t) + (1 − α) ∙ SαX (t) ∙ SαY (t)]. (9) For edge detection, a spatial filter mask is defined as a matrix w of size 𝑚 × 𝑛.The process of spatial filtering consists simply of moving a filter mask w of order 𝑚 × 𝑛 from point to point in an image. Assuming that 𝑚 = 2𝑎 + 1, 𝑛 = 2𝑏 + 1, the smallest meaningful size of the mask is 3 × 3. By moving the window through the whole binary image, the probability of each central pixel of the window can be determined by entropy. Thus, if the gray level of all pixels under the window are homogeneous, 𝑝𝑐 = 1, 𝐻 = 0. In this situation, the central pixel is not an edge pixel. In cases, where 𝑝𝑐 ≤6/9, the variety of gray level of pixels under the window high, and thus we can assume that we are on an edge pixel. 3. Experimental Results and Discussion In order to assess and evaluate the performance of the proposed method, experiments have been performed on the aerial dataset. The performance of the proposed method is assessed qualitatively. (a) (b) (c) Figure 2. Samples of aerial images The following are the experimental results obtined for the tested dateset in figure 1. The data set of aerial images are shown in Figure 2. The subjective comparison of results for the proposed technique of different version of IV images are shown in Figure 3. The results indicate that the proposed technique give a good performance in detecting the edges through consideration of interval concept, which an edges detected have been improved in terms of visual comparison and the boundaries of the objects are more clear in the results of IV images. The results of proposed technique proves that considering the interval arithmetic in designing solutions for some applications may impact the performance of algorithms. 269 Proceedings of the 27th International Symposium Nuclear Electronics and Computing (NEC’2019) Budva, Becici, Montenegro, September 30 – October 4, 2019 Result of IV(L) for image (a) Result of IV(U) for image (a) Result of IV(M) for image (a) Result of IV(L) for image (b) Result of IV(U) for image (b) Result of IV(M) for image (b) Result of IV(L) for image (c) Result of IV(U) for image (c) Result of IV(M) for image (c) Figure 3. Experimental results of aerial images dataset (a-c) As the presented approach may requires a lot of calculations and, as a result, is time consuming especially when it utilizing in proceesing large images to perform the computing task of three version of input image, So, to solve this problem, Its better using the parallel computing which is one of the possible solutions of the problem concerning complex algorithms, as it allows using the available computing resources to the maximum.The use of parallel computing can significantly accelerate the implementation of program, the degree of parallelism and the acceleration is fixed by the number of independent computations performed simultaneously. 4. Conclusion The main goal of this paper is to introduce the application of the interval arithmetic into image processing field, especially images edge detection due to its efficiency in modeling the uncertainties associated with image pixels. We have analyzed the role of the measurement error in digital images and proposing an interval-valued representation of the image to overcome it. An approach for edge detection is presented using interval techniques based on generalized entropy to estimate threshold values required for IV images. The various results obtain of IV images indicate that considering the interval arithmetic in designing solutions for some applications may impact the performance of algorithms. 270 Proceedings of the 27th International Symposium Nuclear Electronics and Computing (NEC’2019) Budva, Becici, Montenegro, September 30 – October 4, 2019 References [1] M. Nachtegael, P. Sussner, T. Melange, E.E. Kerre. Foundations of the Interval-Valued Image Model to Model and Process Uncertainty in Image Capture. IWSSIP 2010 - 17th International Conference on Systems, Signals and Image Processing., Rio de Janeiro, Brazil, June 17-19, 2010. [2] Moore, R.E., Methods and Applications of Interval Analysis. SIAM Studies in Applied Mathematics, Philadelphia. 1979. [3] G. Alefeld and J. Herzberger. "Introduction to Interval Computations". Computer Science and Applied Mathematics, Academic Press, New York, NY, USA, 1983. [4] Aarão Lyra, Roberto CallejasBedregal, Adrião Duarte DóriaNeto, Benjamín René CallejasBedregal. The Interval Digital Images Processing, WSEAS International Conferences of Mathematical Methods And Computational Techniques In Electrical Engineering, Vouliagmeni, Athens, Greece, December 29-31, 2003. [5] Younis Hijazi, Hans Hagen, Charles Hansen, Kenneth I. Joy. Why interval arithmetic is so useful. Conference: Visualization of Large and Unstructured Data Sets, Kaiserslautern, Germany, September 9-11, 2007. [6] L. Jaulin and S. Bazeille. Image shape extraction using interval methods. In Proc. of the 15th IFAC Symposium on System Identification, 2009. [7] Takimoto, R.Y.; Chalella das Neves, A.; Mafalda, R. ; Sato, A.K. ; Tavares, R.S. ; Stevo, N.A.; et al. Detecting Function Patterns with Interval Hough Transform. IEEE International Conference on Industry Applications (INDUSCON), 1 – 5, Sao Paulo, 8-10 Nov. 2010. [8] Teruya Minamoto and Kentaro Aoki, A blind digital image watermarking method using interval wavelet decomposition. International Journal of Signal Processing, Image Processing and Pattern Recognition, Vol. 3, No. 2, June, 2010. [9] M. Galar, E. Barrenechea, J. Fernandez, H. Bustince, G. Beliakov,Representing Images By Means Of Interval-Valued Fuzzy Sets: Application To Stereo Matching. In Ssci 2011 - T2fuzz 2011, 134- 141, Paris, Francia, 2011. [10] S. E. Umbaugh. Computer Imaging: Digital Image Analysis and Processing. CRC Press; 2005. [11] R. C. Gonzalez and R. E. Woods. Digital Image Processing. Prentice Hall,New Jersey; 2008. [12] Scott E Umbaugh. Digital Image Processing and Analysis: Human and Computer Vision Applications with CVIP tools, Second Edition, CRC Press; 2010. [13] C. Lopez-Molina, B. De Baets, E. Barrenechea, and H. Bustince. Edge Detection on Interval Valued Images. Advances in Intelligent and Soft Computing, Vol. 107, 2012, 325-337. [14] M. Nachtegael, P. Sussner, T. Melange , E.E. Kerre. Foundations of the Interval-Valued Image Model to Model and Process Uncertainty in Image Capture. IWSSIP 2010 - 17th International Conference on Systems, Signals and Image Processing. June 17-19, 2010, Rio de Janeiro, Brazil. [15] A. Elaraby; A. Nechaevskiy: An Image Verification Framework Development, GRID 2018, Dubna, Russia. [16] El-Owny, H.; A. Elaraby: Improved Generalized Interval Arithmetic, International Journal of Mathematics and Computation,Vol. 19; 2, 2013. [17] A. Elaraby; David Moratal: A Generalized Entropy-Based Two-Phase Threshold Algorithm for Noisy Medical Image Edge Detection. Scientia Iranica, Vol. 24; 6, 2017. [18] Gray, R.M., Entropy and Information Theory, Springer (2013). 271