Acta Polytechnica DOI:10.14311/AP.2019.59.0593 Acta Polytechnica 59(6):593–600, 2019 © Czech Technical University in Prague, 2019 available online at https://ojs.cvut.cz/ojs/index.php/ap OPTIMIZATION OF COMPUTATIONAL BURDEN OF THE POINT INFORMATION GAIN Jan Urban∗, Renata Rychtáriková, Petr Macháček, Dalibor Štys, Pavla Urbanová, Petr Císař University of South Bohemia in České Budějovice, Faculty of Fisheries and Protection of Waters, South Bohemian Research Center of Aquaculture and Biodiversity of Hydrocenoses, Kompetenzzentrum MechanoBiologie in Regenerativer Medizin, Institute of Complex Systems, Zámek 136, 373 33 Nové Hrady, Czech Republic ∗ corresponding author: urbanj@frov.jcu.cz Abstract. We developed a method of image preprocessing based on the information entropy, namely, on the information contribution made by each individual pixel to the whole image or to image’s part (i.e., a Point Information Gain; PIG). An idea of the PIG calculation is that an image background remains informatively poor, whereas objects carry relevant information. In one calculation, this method preserves details, highlights edges, and decreases random noise. This paper describes optimization and implementation of the PIG calculation on graphical processing units (GPU) to overcome a high computational burden. Keywords: Pixel information contribution, entropy, image analysis, computation optimization. 1. Introduction One of the tasks in image analysis is an accurate seg- mentation of entities from their background. Correct finding of objects depends on plenty of factors, such as the kind of illumination, shadows, level of noise, proper focusing, overlaps of objects, and dissimilarity between an object and its background. The tradi- tional methods, e.g., thresholding or edge detectors, are generally based on local or global characteristics of intensity histograms [1–4]. The final result of a chosen segmentation algorithm is more or less condi- tioned by the sufficiency of preprocessing computation that include color space transformations, denoising, or other adjustments [5–7]. The segmentation process is of a high quality if the borders of the objects of interest are sharp, clearly visible, and separated from the background. A promising way for automation of the whole pro- cess of the selection of a sub-image of proper parame- ters is a usage of an equation of information entropy, which was defined by Shannon and generalized by Rényi [8]. Although the formula for the information entropy is well known for a longer time, other ways how to use it for one or two dimensional thresholding and filtering, e.g., [1–4, 9–11], still appear. The en- tropy also generally measures an information content. An important question is how much information is included in a data point and how the points can be dis- tinguished from each other. This question was solved by a derivation of the variable Point Information Gain (PIG, Γ) [12–22] which evaluates an information con- tent of a single pixel in local and global context. This variable says how much is one individual pixel impor- tant for understanding of an image or image’s part. In addition, the method of the PIG preserves the details, highlights the edges, and decreases random noise in one calculation. Examples of usage of the PIG in im- age (pre)processing were published previously [12–22] The computation tool for image preprocessing using the PIG method is called the Image Info Extractor Professional software (IIEP; Institute of Complex Sys- tems, Nové Hrady). The theoretical concept and practical utilization of this kind of software was in- troduced previously and this paper is supplemental to [17]. The task of this paper is, using the examples of the Shannonian PIG with whole image approach and for cross neighbourhood for each pixel, to present a kind of computational optimization and the imple- mentation of this computation on GPUs in order to achieve a higher computation performance of the IIEP software. 2. The Shannon entropy The Shannon entropy is a special case of the Rényi en- tropy for α = 1. Any discrete probability distribution P = {p0,p1, ...,pk} fulfils the condition pj ≥ 0; k∑ j=1 pj = 1. (1) In an intensity image, the approximation of the prob- ability distribution is given by the histogram function that shows counts of the pixels Φ(x,y) with intensity j at the position (h,w) in the image [3, 4]. More conditions are assumed when measuring the information. The information must be additive for two independent events with the probabilities of oc- currence of p1 and p2: I(p1,2) = I(p1) + I(p2). (2) 593 https://doi.org/10.14311/AP.2019.59.0593 https://ojs.cvut.cz/ojs/index.php/ap J. Urban, R. Rychtáriková, P. Macháček et al. Acta Polytechnica The information itself is dependent only on the prob- ability distribution or, as in our case, on normal- ized histogram function. Eq. 2 describes a modified Cauchy’s functional equation with the unique solution I(p1) = −K×log2(p1). In statistical thermodynamics, the constant K refers to the Boltzmann constant [23], in the Hartley information, K = 1 [24]. If different amounts of information occur with different proba- bilities, the total amount of information corresponds to the average of the individual information contribu- tions weighted by the probabilities of their individual occurrences [24–26]. This leads to the definition of the Shannon information entropy as∑ j (pjIj ); H (P) = − ∑ j pj log2(pj ). (3) The image histogram N is normalized to the total amount of pixels [27, 28] to fulfil the condition (1): N =  ∑ h,w n0(h,w), ∑ h,w n1(h,w), . . . ∑ h,w nk(h,w)   ; nj(h,w) = { 1 for Φ(h,w) = j 0 for Φ(h,w) 6= j. (4) pj(h,w) = nj(h,w) WH ; P =  ∑ h,w p0(h,w), ∑ h,w p1(h,w), . . . ∑ h,w pk(h,w)   , where WH is a total amount of pixels in an image of the size of [H ×W ]. Then, the normalized histogram function P is used to define the information in the form of the Shannon entropy as H (P) = − ∑ j pj log2 pj. (5) For the simplification of the next deduction, the binary logarithm log2, which explains the information in bits, is supplied by natural algorithm ln. 3. Point Information Gain In the form of the variable PIG (Γ(i)), the Shannon entropy allows to measure an information content of either the whole image or a selected part of the image. The key idea for the definition of the PIG was if the occurrence of the intensity of a single pixel is a surprise. One can predict that, on the one hand, the background pixels will not carry much information and, on the other hand, the pixels of structurally complicated objects will increase the entropy on their positions after discarding one of them. In order to investigate the contribution of one single pixel with intensity value i to the total entropy, it is necessary to introduce a histogram N(i), which is created without this investigated pixel: n (i) j = { nj for j 6= i nj − 1 for j = i. The intensity value i of the investigated pixel Φ(h,w) = Φ(x,y) was now discarded from the computation, but only once. One single pixel of intensity j will only decrease the histogram value n(i)j on its intensity po- sition i. Then, the histogram is normalized according to condition (1). The probability (value of the normal- ized histogram) p(i)i of the intensity i is slightly lower than the probability pi of the primary normalized histogram P (with all pixels). The other probabili- ties p(i)j , where j is not the value of the investigated pixel i, are slightly higher than the probability pj of the primary normalized histogram P (with all pix- els). Then, the second Shannon information entropy H (P(i)) without the pixel of intensity i at the posi- tion (x,y) is computed from the modified normalized histogram P (i) as H (P(i)) = − ∑ j p (i) j ln(p (i) j ), (6) where the individual information contributions ln(p(i)j ) as well as their weights p(i)j slightly differ from those in the Shannon information entropy H (P) (Eq. 5). Thus, using Eqs. (5)–(6), we obtained two different values of the information entropy: The entropy H (P) represents the total information in the whole original image, whereas the entropy H (P(i)) represents the information in the image without the investigated pixel. Γ(i) = H (P) − H (P(i)) = H − H (i) (7) refers then to a difference between the entropy of the two histograms and thus also to the difference be- tween the entropy of two images – with and without the investigated pixel Φ(x,y) of the intensity i. Recall that the histograms P and P(i) were normalized and, therefore, the difference Γ(i) is usually a small number. (In the IIEP software, the Point Information Gain is defined with the opposite sign as Γ(i) = H (i) − H .) The difference Γ(i) represents either the entropy con- tribution of the pixel Φ(x,y) or the contribution of the intensity value of the pixel Φ(x,y) to the information content of the image. In other words, the transforma- tion of the intensity value of the pixel Φ(x,y) value to its contribution to the image via Eq. (7) represents the information contribution carried by this pixel. The computation of the Γ(i) for each single pixel trans- forms an original image into an entropy map, i.e., into an image that shows the contribution of each pixel to the total information content of the image. The variable Γ(i) is dependent only on the intensity of the pixel Φ(x,y) and does not carry any information about the pixel’s position. However, the histogram can include pixels from not only the whole image but also from a selected area around an investigated pixel. If the image has a semi-uniform background with changes in intensity and the background is com- pletely different in different parts of the image, it is 594 vol. 59 no. 6/2019 Optimization of computational burden of the Point Information Gain advantageous to use the row and the column with the investigated pixel in the centre as the area for the computation of the intensity histogram N = N(x) + N(y) − Ei, (8) where the value of pixel Φ(x,y) is counted only once. The value of the second pixel Φ(x,y) is subtracted using the unit histogram Ei = [0, 0, . . . , 1, . . . , 0, 0] with 1 at the position relevant to nj = ni > 0. The outputs consist of the amount of information for the cross centred on the investigated pixel itself. The additional histogram is again a histogram of the values from the cross, however, in this case, the intensity value of the center pixel Φ(x,y) was discarded: N(i) = N(x) + N(y) − 2Ei. (9) The subsequent application of Eq. (5) results in en- tropies H(x,y)(P ) = H(x,y) and H(x,y)(P (i)) = H (i) (x,y) with and without the center pixel, respectively. The difference Γ(i)(x,y) = H(x,y) − H (i) (x,y) refers to the dif- ference between the information content of these two crosses. Recall again that the difference Γ(i)(x,y) is a small number and represents either the entropy contri- bution of pixel Φ(x,y) or the contribution of the value of pixel Φ(x,y) to the cross. Both (whole and cross) PIG can be considered as special cases of the Kullback-Leibler divergence [29] of two distributions: one distribution is formed from the neighbourhood of the investigated pixel including this pixel, while the second distribution is formed from the same neighbourhood but without this pixel. The whole approach considers the whole image as the neighbourhood, while the cross approach considers the designed cross with the investigated pixel in the center. Thus, the novelty of the PIG approach lies in the practical definition of the investigated normalized dis- tributions. 4. Optimization of the algorithm 4.1. Point Information Gain for the whole image The Γ(i) values for the whole image does not need to be computed for each pixel repeatedly. The value of the total entropy H remains the same through the whole image and the value of the entropy H (i) is the same for all pixels Φ(x,y) with the same intensity j = i. The algorithm was optimized by the modification of the relevant equations as follows: The histogram N = [n0,n1, . . .n2d−1] for the whole image was redefined to nj = ||{∀(x,y) : Φ(x,y) = j ∧x ∈{1, 2, . . . ,H} ∧y ∈{1, 2, . . . ,W}}||; j = [0, 1, . . . , i, . . . , 2d − 1]. The entropy H can be subsequently explained as H = − 2d−1∑ j=0 pj ln(pj ), H = − 2d−1∑ j=0 nj WH ln ( nj WH ) , H = − 2d−1∑ j=0 nj WH [ln(nj ) − ln(WH)], H = ln(WH) WH 2d−1∑ j=0 nj ︸ ︷︷ ︸ W H − 1 WH 2d−1∑ j=0 nj ln(nj ), H = ln(WH) − 1 WH 2d−1∑ j=0 nj ln(nj ). (10) The function H (i) which explains the entropy of the modified image with the omitted investigated pixel Φ(x,y) was reformulated as H (i) = − 2d−1∑ j=0 p (i) j ln(p (i) j ), H (i) = − 2d−1∑ j=0 n (i) j WH − 1 ln ( n (i) j WH − 1 ) , H (i) = − 2d−1∑ j=0 n (i) j WH − 1 [ln(n(i)j ) − ln(WH − 1)], H (i) = ln(WH − 1) WH − 1 2d−1∑ j=0 n (i) j︸ ︷︷ ︸ W H−1 − ∑2d−1 j=0 n (i) j ln(n (i) j ) WH − 1 , H (i) = ln(WH − 1) − ∑2d−1 j=0 n (i) j ln(n (i) j ) WH − 1 . (11) The histogram N(i) is then defined as n (i) j = { nj j 6= i nj − 1 j = i, j = [0, 1, . . . , 2d − 1]. The first optimization was performed as n(i) ⇔ H (i) ⇔ Φ(x,y) = i; x ∈{1, 2, . . . ,H}; y ∈{1, 2, . . . ,W}; i ∈{0, 1, . . . , 2d − 1}. 595 J. Urban, R. Rychtáriková, P. Macháček et al. Acta Polytechnica Figure 1. Image of the size of [H × W] with the intensity levels of d bits. From this optimization as well as Eq.(7) follows di- rectly that the entropy H (i) is dependent only on the intensity i of the pixel Φ(x,y) and not on the pixel’s position (x,y) in the image. Then, the entropy H (i) can be redefined as H (i) = (H (i)|Φ(x,y) = i); i = [0, 1, . . . , 2d − 1]. Eventually, the PIG for the whole image is subse- quently explained as Γ(i) = H − H (i), Γ(i) = ln(WH) − ∑2d−1 j=0 nj ln(nj ) WH − ln(WH − 1) + ∑2d−1 j=0 n (i) j ln(n (i) j ) WH − 1 , Γ(i) = ln ( WH WH − 1 ) − ni ln(ni) + ∑i−1 j=0 nj ln(nj ) + ∑2d−1 j=i+1 nj ln(nj ) WH + (ni − 1) ln(ni − 1) WH − 1 + ∑i−1 j=0 nj ln(nj ) + ∑2d−1 j=i+1 nj ln(nj ) WH − 1 , Γ(i) = ln ( WH WH − 1 ) + 1 WH(WH − 1)  i−1∑ j=0 nj ln(nj ) + 2d−1∑ j=i+1 nj ln(nj )   ︸ ︷︷ ︸∑2d −1 j=0 (nj ln(nj ))−ni ln(ni) − ni ln(ni) WH + (ni − 1) ln(ni − 1) WH − 1 , Figure 2. Image of the size of [H × W] with the intensity levels of d bits, with investigated cross. Γ(i) = ln ( WH WH − 1 ) + ∑2d−1 j=0 nj ln(nj ) WH(WH − 1) + 1 WH − 1 [(ni − 1) ln(ni − 1) −ni ln(ni)] , Γ(i) = ln ( WH WH − 1 ) + ∑2d−1 j=0 nj ln(nj ) WH(WH − 1) + 1 WH − 1 ln (ni − 1)(ni−1) n (ni) i . (12) From Eq. 12 follows that the Γ(i) can be evaluated as Γ(i) = B + C ln (ni − 1)(ni−1) n (ni) i , (13) where the constant C = 1 W H−1 and the base B = ln ( W H W H−1 ) + 1 W H(W H−1) ∑2d−1 j=0 nj ln(nj ). 4.2. Point Information Gain for the cross computation A column histogram N(y) is defined as N(y) = [n0(y),n1(y), . . . ,n(2d−1)(y)]; y = [1, 2, . . . ,W ]; j = [0, 1, . . . , i, . . . , 2d − 1]. Similarly, a row histogram N(x) is defined as N(x) = [n0(x),n1(x), . . . ,n(2d−1)(x)]; x = [1, 2, . . . ,H]; j = [0, 1, . . . , i, . . . , 2d − 1]. The elements of the unit histogram Ei are (cf. Eqs. (8)–(9)) ej = { 0 j 6= i = Φ(x,y) 1 j = i = Φ(x,y) j = [0, 1, . . . , i, . . . , 2d − 1]. 596 vol. 59 no. 6/2019 Optimization of computational burden of the Point Information Gain The entropy H(x,y) for computation from the col- umn histogram N(y) and row histogram N(x) of the cross with the center pixel on, of the intensity i at the position (x,y), can be written as H(x,y) = − 2d−1∑ j=0 pj ln(pj ), H(x,y) = = − 2d−1∑ j=0 nj(x) + nj(y) −ej H + W − 1 ln nj(x) + nj(y) −ej H + W − 1 , H(x,y) = = 2d−1∑ j=0 nj(x) + nj(y) −ej H + W − 1 ln(H + W − 1) − 2d−1∑ j=0 nj(x) + nj(y) −ej H + W − 1 ln(nj(x) + nj(y) −ej ), H(x,y) = = ln(H + W − 1) H + W − 1 2d−1∑ j=0 nj(x) + nj(y) −ej︸ ︷︷ ︸ H+W −1 − ∑2d−1 j=0 (nj(x) + nj(y) −ej ) ln(nj(x) + nj(y) −ej ) H + W − 1 , H(x,y) = = ln(H + W − 1) − ∑2d−1 j=0 (nj(x) + nj(y) −ej ) ln(nj(x) + nj(y) −ej ) H + W − 1 , H(x,y) = = ln(H + W − 1) − ∑i−1 j=0 (nj(x) + nj(y)) ln(nj(x) + nj(y)) H + W − 1 (14) − ∑2d−1 j=i+1 (nj(x) + nj(y)) ln(nj(x) + nj(y)) H + W − 1 − (ni(x) + ni(y) − 1) ln(ni(x) + ni(y) − 1) H + W − 1 . Similarly, the entropy H (i)(x,y) for the computation from the column histogram N(y) and row histogram N(x) of the cross without center pixel, of the intensity i at the position (x,y), is H (i) (x,y) = − 2d−1∑ j=0 p (i) j ln(p (i) j ), H (i) (x,y) = = − 2d−1∑ n=0 nj(x) + nj(y) − 2ej H + W − 2 ln nj(x) + nj(y) − 2ej H + W − 2 , H (i) (x,y) = ln(H + W − 2) − ∑2d−1 j=0 (nj(x) + nj(y) − 2ej ) ln(nj(x) + nj(y) − 2ej ) H + W − 2 , H (i) (x,y) = = ln(H + W − 2) − ∑i−1 j=0 (nj(x) + nj(y)) ln(nj(x) + nj(y)) H + W − 2 − ∑2d−1 j=i+1 (nj(x) + nj(y)) ln(nj(x) + nj(y)) H + W − 2 . (15) It gives a PIG for the cross computation as Γ(i)(x,y) = H(x,y) − H (i) (x,y), Γ(i)(x,y) = = ln ( H + W − 1 H + W − 2 ) + ∑i−1 j=0 (nj(x) + nj(y)) ln(nj(x) + nj(y)) (H + W − 1)(H + W − 2) + ∑2d−1 j=i+1 (nj(x) + nj(y)) ln(nj(x) + nj(y)) (H + W − 1)(H + W − 2) (16) − (ni(x) + ni(y) − 1) H + W − 1 ln(ni(x) + ni(y) − 1) + (ni(x) + ni(y) − 2) H + W − 2 ln(ni(x) + ni(y) − 2). Let us introduce the vector t defined as t =[t(0), t(1), t(2), . . . , t(H+W −1)] = =[0 ln(0), 1 ln(1), 2 ln(2), . . . , (H + W − 1) ln(H + W − 1)]. Then, Eq. (16) can be written as Γ(i)(x,y) = = ln ( H + W − 1 H + W − 2 ) + ∑i−1 j=0 t(nj(x)+nj(y)) (H + W − 1)(H + W − 2) (17) + ∑2d−1 j=i+1 t(nj(x)+nj(y)) (H + W − 1)(H + W − 2) − t(ni(x)+ni(y)−1) H + W − 1 + t(ni(x)+ni(y)−2) H + W − 2 . 597 J. Urban, R. Rychtáriková, P. Macháček et al. Acta Polytechnica In this way, the time consuming computation of the logarithms was replaced by the summing of pre- computed vectors k ln(k). The length of the vector t does not depend on the number of pixels in the image but on the dimensions (sizes of the sides) of the image. The number of rows and columns of the image determines how many points in the histogram created from the cross is available. It is, however, possible that some values in the vector t will never be used in the computation. Nevertheless, due to the possibility of searching in the list of all stored k ln(k), the approach of the precomputed histograms makes the computation faster. Eq. (17) implicates Γ(i)(x,y) = C (x,y) + B(x,y) + F (x,y); C(x,y) = ln ( H + W − 1 H + W − 2 ) ; B(x,y) = ∑i−1 j=0 (nj(x) + nj(y)) ln(nj(x) + nj(y)) (H + W − 1)(H + W − 2) + ∑2d−1 j=i+1 (nj(x) + nj(y)) ln(nj(x) + nj(y)) (H + W − 1)(H + W − 2) ; (18) Fi = (ni(x) + ni(y) − 2) ln(ni(x) + ni(y) − 2) H + W − 2 − (ni(x) + ni(y) − 1) ln(ni(x) + ni(y) − 1) H + W − 1 . In Eq. 18 the term C(x,y) is a constant, the B(x,y) is a base of the computation, and the Fi corresponds to a fluctuating part of the computation. 5. Implementation on GPU The algorithm optimised above can be further split into a few threads when multi-core CPUs can be fully utilized, however this is relevant mainly for batch pro- cessing of image sets. The computation process was further optimized by an implementation on graph- ics cards [30]. The algorithm was executed using the CUDA architecture to run on NVIDIA hardware. The key to the next acceleration was to fit the algorithm to GPU highly-parallel architecture which is typical of a double hierarchy. All multiprocessors can access data to the device memory. In the CUDA data-parallel programming, the data has to be split into two levels of algorithmically independent parts, into a grid of blocks where a kernel processes the block with the same algorithm. During the processing of the block, several threads run – the second level of the hierarchy. All threads of one block run per one multiprocessor. The IIEP software tries to detect the graphics card with the CUDA support and, if the card is available, the calculation is realised as the parallel computation on the graphics card kernels (GPU). Depending on the image resolution and the type of the entropy cal- culation, the calculation is typically 50–150× faster on the GPU than on the CPU. The original concept of the software expected an 8-bpc (bits per channel) im- ages (which could be optimized directly for the GPU memory block), while the current cameras are also able to provide raw file formats with ≥10 bpc (which requires a different GPU static-field allocation). The possibility to work with the raw data files deals with signal processing without debayerization [14]. 6. Conclusion We investigated the degree of modality for a compu- tation of the difference of two entropies: H , entropy with a central pixel Φ(x,y), and H (i), entropy without such pixel. An output image then represents a map of pixels’ importance. We simplified the calculation of the information contribution of a pixel to the whole Shannonian information of the image and to local information explained for pixels lying on shanks cross- ing the studied pixel Φ(x,y). The pre-computation of a fixed set (for a given bit precision) of possible logarithm values reduces the total number of neces- sary calculations in the algorithm and decrease the computational burden in the evaluation of the entropy difference. The calculation kernel was implemented for hardware acceleration using a graphics card. List of symbols B Base in computation of Γ(i) B(x,y) Base in computation of Γ (i) (x,y) C Constant member in computation of Γ(i) C(x,y) Constant member in computation of Γ (i) (x,y) CUDA Compute Unified Device Architecture d Image intensity bit depth ej Element of the unit vector Ei Ei Unit vector [0,0, . . . ,1,. . . ,0,0], where 1 is at the position ei Fi Fluctuating in computation of Γ (i) (x,y) GPU Graphical Processing Unit h Row position of the pixel of intensity j H Image height (in pixels) H (P) = H Shannon entropy for probability histogram function of the whole image H(x,y) Shannon entropy for probability histogram func- tion from the cross around an investigated pixel of the intensity i at the position (x,y) H (P(i)) = H (i) Shannon entropy for probability his- togram function from the whole image without an in- vestigated pixel of intensity i H (i) (x,y) Shannon entropy for probability histogram func- tion from the cross around and without an investigated pixel of the intensity i at the position (x,y) i Intensity of an investigated pixel I Information IIEP Image Info Extractor Professional software j Pixel intensity; j ∈{0, 1, . . . , i, . . . , i, . . . ,k} K Weight of the entropic contribution; e.g., K = 1 in the Hartley and Shannon entropy; K = 1.38 × 10−23 in the Boltzmann entropy nj(h,w) = nj Contribution of the pixel of intensity j at the position (h,w) to the histogram N 598 vol. 59 no. 6/2019 Optimization of computational burden of the Point Information Gain n (i) j Element in the histogram N, where a pixel of inten- sity i is discarded nj(x) Element of the intensity histogram of an image pixel row x nj(y) Element of the intensity histogram of an image pixel column y N Image histogram function N(i) Intensity histogram without an investigated pixel of intensity i N(x) Intensity histogram for the image pixel row x N(y) Intensity histogram for the image pixel column y pi Probability of the occurrence of the investigated pixels of intensity i in histogram P pj(h,w) = pj Contribution of the pixel of intensity j at the position (h,w) to the probability histogram P ; p (i) j Element in the probability histogram P, where the pixel of intensity i is discarded P Discrete probability distribution (of the whole image) P(i) Probability intensity histogram without an investi- gated pixel of the intensity i PIG Point Information Gain; Γ t Mathematical substitution for a vector of weighted logarithms with element t(nj ) = nj ln nj t(nj ) Element of the vector t of weighted logarithms w Column position of the pixel of intensity j W Image width (in pixels) x Row position of the pixel of intensity i y Column position of the pixel of intensity i α Rényi dimensionless coefficient Γ(i) Point Information Gain for a pixel of intensity i (from a whole-image histogram) Γ(i)(x,y) Point Information Gain for a pixel of intensity i from a histogram from pixels forming a cross around the investigated pixel Φ(h,w) Pixel of intensity j at the position (h,w) Φ(x,y) Pixel (of) intensity i at the position (x,y) Acknowledgements Authors are thankful to J. Vaněk, T. Levitner, A. Zhy- rova, and V. Březina for several discussions. This work was supported by the Ministry of Education, Youth and Sports of the Czech Republic—projects CENAKVA (LM2018099) and the CENAKVA Centre Development (No. CZ.1.05/2.1.00/19.0380)—and from the European Regional Development Fund in frame of the project Kom- petenzzentrum MechanoBiologie (ATCZ133) in the Inter- reg V-A Austria–Czech Republic programme. The work was further financed by the TA CR Gama PoC 03-24- Rychtáriková sub-project. References [1] S. Beucher. Applications of mathematical morphology in material sciences: A review of recent developments. international metallography conference, colmar, france. Proc MC95 pp. 41–46, 1945. [2] N. Otsu. A threshold selection method from gray-level histogram. IEEE Trans Syst Man Cybern 9(1):62–66, 1979. doi:10.1109/TSMC.1979.4310076. [3] M. Sonka, V. Hlavac, R. Boyle. Image processing, analysis and machine vision. Brooks/Cole Publishing Company, 1999. [4] R. C. Gonzales, R. E. Woods. Digital image processing. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1992. [5] J. Yang, W. Lu, A. Waibel. Skin-color modeling and adaptation. Proc. ACCV 1998-Vol. II. Lect Notes Comp Sci 1352:687–694, 1998. doi:10.1007/3-540-63931-4_278. [6] L. Vincent. Morphological grayscale reconstruction in image analysis: applications and efficient algorithms. IEEE Trans Image Process 2(2):176–201, 1993. doi:10.1109/83.217222. [7] J. Vaněk, J. Urban, Z. Gardian. Automated detection of photosystems II in electron microscope photographs. Technical Computing Prague, Prague, Czechia pp. 102–105, 2006. [8] A. Rényi. On measures of information and entropy. Proc 4th Berkeley Symp Math Stat Prob 1:547–561, 1961. [9] R. Moddemeijer. On estimation of entropy and mutual information of continuous distributions. Signal Process 16(3):233–246, 1989. doi:10.1016/0165-1684(89)90132-1. [10] T. Pun. A new method for grey-level picture thresholding using the entropy of the histogram. Signal Process 2(3):223–237, 1980. doi:10.1016/0734-189X(85)90125-2. [11] P. Iliev, P. Tzvetkov, G. Petrov. Multidimensional dynamic scene analysis using 3D image histogram and entropy sequences analysis (bulgarian). Int J Comp 6(1):35–43, 2007. [12] A. Zhyrova, D. Stys, P. Cisar. Information entropy approach as a method of analysing Belousov-Zhabotinsky reaction wave formation. Chem Listy 107(Suppl. 3):S341–S342, 2013. [13] R. Rychtáriková. Clustering of multi-image sets using rényi information entropy. In F. Ortuño, I. Rojas (eds.), IWBBIO 2016, Lect Notes Bioinf, vol. 9656, pp. 517–526. 2016. doi:10.1007/978-3-319-31744-1_46. [14] R. Rychtáriková, T. Náhlík, K. Shi, et al. Super- resolved 3-D imaging of live cell’s organelles from bright- field photon transmission micrographs. Ultramicroscopy 179:1–14, 2017. doi:10.1016/j.ultramic.2017.03.018. [15] A. Zhyrova, D. Štys. Construction of the phenomenological model of Belousov-Zhabotinsky reaction state. Int J Comp Math 91(1):4–13, 2014. doi:10.1080/00207160.2013.766332. [16] D. Štys, J. Urban, R. Rychtáriková, et al. Measurement in biological systems from the self-organisation point of view. In F. Ortuño, I. Rojas (eds.), IWBBIO 2015, Lect Notes Bioinf, vol. 9044, pp. 431–443. 2015. doi:10.1007/978-3-319-16480-9\_43. [17] R. Rychtáriková, J. Korbel, P. Macháček, et al. Point information gain and multidimensional data analysis. Entropy 18(10):372, 2016. doi:10.3390/e18100372. [18] T. Náhlík, J. Urban, P. Císař, et al. Entropy based approximation to cell monolayer development. In A. Jobbággy (ed.), 5th IFMBE, IFMBE Proc., vol. 37, pp. 563–566. 2011. doi:10.1007/978-3-642-23508-5_146. 599 http://dx.doi.org/10.1109/TSMC.1979.4310076 http://dx.doi.org/10.1007/3-540-63931-4_278 http://dx.doi.org/10.1109/83.217222 http://dx.doi.org/10.1016/0165-1684(89)90132-1 http://dx.doi.org/10.1016/0734-189X(85)90125-2 http://dx.doi.org/10.1007/978-3-319-31744-1_46 http://dx.doi.org/10.1016/j.ultramic.2017.03.018 http://dx.doi.org/10.1080/00207160.2013.766332 http://dx.doi.org/10.1007/978-3-319-16480-9\_43 http://dx.doi.org/10.3390/e18100372 http://dx.doi.org/10.1007/978-3-642-23508-5_146 J. Urban, R. Rychtáriková, P. Macháček et al. Acta Polytechnica [19] T. Náhlík, D. Štys. Microscope point spread function, focus and calculation of optimal microscope set-up. Int J Comp Math 91(2):221–232, 2014. doi:10.1080/00207160.2013.851379. [20] J. Urban, J. Vanek, D. Stys. Preprocessing of microscopy images via shannon’s entropy. PRIP 2009, Belarusian State University, Belarussia. Proc PRIP 2009 pp. 183–187, 2009. [21] J. Urban, J. Vaněk. Preprocessing of microscopy images via Shannon’s entropy on GPU. GraVisMa 2009, Pilsen, Czechia. Workshop Proc pp. 48–51, 2009. [22] J. Urban, J. Vaněk, D. Stys. Preprocessing of microscopy images via Shannon’s entropy, ÖAGM/AAPR Workshop, Graz, Austria. ÖAGM/AAPR Workshop pp. 48–51, 2011. [23] T. Boublík. Statistická termodynamika (Czech). Statistical Thermodynamics. Academia, Prague, Czechia, 1996. [24] P. Jizba, T. Arimitsu. The world according to Rényi: thermodynamics of multifractal systems. Ann Phys 312(1):17–59, 2004. doi:10.1016/j.aop.2004.01.002. [25] C. E. Shannon. A mathematical theory of communication. Bell Syst Techn J 27(3):379–423, 1948. doi:10.1002/j.1538-7305.1948.tb01338.x. [26] C. E. Shannon. A mathematical theory of communication. Bell Syst Techn J 27(4):623–656, 1948. doi:10.1002/j.1538-7305.1948.tb00917.x. [27] O. Demirkaya, M. H. Asyali, P. K. Sahoo. Image processing with Matlab: Applications in medicine and biology. CRC Press, 2009. [28] M. Nixon, A. Aguado. Feature extraction & image processing. Academic Press, 2002. [29] S. Kullback, R. A. Leibler. On information and sufficiency. Ann Math Stat 22(1):79–86, 1951. doi:10.1214/aoms/1177729694. [30] General-purpose computation using gpus. www.gpgpu.org. 600 http://dx.doi.org/10.1080/00207160.2013.851379 http://dx.doi.org/10.1016/j.aop.2004.01.002 http://dx.doi.org/10.1002/j.1538-7305.1948.tb01338.x http://dx.doi.org/10.1002/j.1538-7305.1948.tb00917.x http://dx.doi.org/10.1214/aoms/1177729694 www.gpgpu.org Acta Polytechnica 59(6):593–600, 2019 1 Introduction 2 The Shannon entropy 3 Point Information Gain 4 Optimization of the algorithm 4.1 Point Information Gain for the whole image 4.2 Point Information Gain for the cross computation 5 Implementation on GPU 6 Conclusion List of symbols Acknowledgements References