-Image processing techniques are important algorithm both in applied mathematics and various aspects of computer science. The aim of this paper is to present the algorithm composing an image from the parts. We consider two cases. First, when the image is divided only vertically, and second, when the image is divided vertically and horizontally. We discuss our algorithm and also present appropriate statistics associated with the program's running time. Index Terms-image processing, Mathematica, images, composing algorithm
I. INTRODUCTION
In today’s world, computers play a very important role. They are used in every area of life and science. Today, artificial intelligence (AI) is one of the major directions of science. These methods combined with developing computer technology create enormous opportunities for science.
Nowadays, image processing is among rapidly growing technologies. It forms core research area within engineering and computer science disciplines too. Digital image processing techniques help in manipulation of the digital images by using computers. These techniques have many advantages over analog image processing because computer allows a much wider range of algorithms to be applied to the input data. For example, pattern recognition uses algorithms such as neural networks, which are based on machine learning.
A very wide introduction to various image processing
techniques was presented in [
Techniques of image processing use mathematical operations on matrices of images (because as we will see in section II, every digital image can be represented as a matrix). For example in application of filters in image processing, the values of points from its environment are taken into account in calculating the new value of the point. In this paper we present a proposal of the algorithm composing an image from the parts. The paper presents a simulation on composing puzzles from various images by the use of our method, where we compare significant pixels that match object shapes. We compare some features that describe complexity of this method and discuss its potential benefits.
The images we see on internet pages and the photos we take with our mobile phones are examples of digital images. It is possible to represent this kind of images using matrices. Mathematically the image can be seen as the matrix 3 f12 : : : f1M f22 : : : f2M
... . . . ... fN2 : : : fNM where fij ; i = 1; : : : ; N; j = 1; : : : ; M represent colors of the pixels, N and M are sizes of image (respectively vertical and horizontal) given in pixels. Generally fij can be the vectors describing color in certain system (for example RGB). But in this paper we assume that for all images every fij is a number, which describe color in a greyscale, where set f0; 1; : : : ; 255g is transformed into f0; : : : ; 1g. By this representation it is obvious, that we can operate on image using mathematical operations on its matrix.
Our algorithm is based on comparison of border pixels of components of image. As an input we take table of components of image in any order. In this paper M denotes table of transformations of those components into their matrix representations.
First we will present an algorithm for the case when the image is divided only vertically, so all components are strips with the same height as the image.
In the first step we create a matrix E of errors, where eij is an error between right side of Mi and left side of Mj , in the following way. For a diagonal of E we take a maximal value 1, because we do not want to link component of image with itself. For other elements mean value of difference between corresponding border pixels is computed.
In the second step we find coordinates i; j in the matrix E with minimal value of E, it means the images with "the best fit". We join the matrices of these images, it is Mi with Mj , which corresponds to the merging of these images. The new component replace Mi and Mj is deleted from M . Additional change to matrix E occurs: column i is replaced by column j and column j and line j are deleted, then diagonal elements of this matrix are changed to 1 again. We could compute the matrix E after every merge of components of images but transformation described above give us the same result and decreases amount of necessary computations. In package Mathematica this step can be realized in the following way E1=E; Do[
If[E1[[i, j]] == Min[E],
joinl = M[[i]]; joinr = M[[j]];
M[[i]] = Join[joinl, joinr, 2]; M = Delete[M, j];
E[[i]] = E[[j]];
E = Drop[E, {j}, {j}];
Break]; , {j, 1, Length[M]}] , {i, 1, Length[M]}]; Do[E[[i, i]] = 1, {i, 1, Length[E]}];
Next second step is repeated with table M and matrix E adjusted in previous iteration. The implementation of the described technique is presented in following algorithm Input: Table M of images 1: r := lenght of M 2: mv := vertical dimension of all Mi 3: Creating the matrix E 4: for i = 0; i r do 5: for j = 0; j r do 6: if i 6= j then 1 Xmv jMi(k; 1)
Mj (k; 1)j 7: 8: 9: else eij := eij := 1 r k=1 10: end if 11: end for 12: end for 13: for k = 1; k < r do 14: n := length of M 15: min := Minimum value of E 16: for i = 0; i n do 17: for j = 0; j n do 18: if eij = min then 19: replace Mi by joined Mi with Mj 20: delete Mj from M 21: replace in E column i by column j 22: delete column j and line j from E 23: break the loop 24: else 25: do nothing 26: end if 27: end for 28: end for 29: for i = 1; i lenght of E do 30: eii := 1 31: end for 32: end for Output: M
In the second case, when the image is divided vertically and horizontally into rectangles of the same dimensions, we use modified algorithm.
As an input we take table M of components of image in any order and number of rows (the number of parts into which the image was divided horizontally). First we compute width of image. To obtain this we sum width of all components and divide it by number of rows. Now we create the matrix E of errors in the same way as in the algorithm for strips. Next we execute Algorithm 1, with one modification, until the same number of components as number of rows remains. At the end of the second step of the Algorithm 1 we check width of component Mi which is result of this step. If it is less than width of image then we proceed the next step. Otherwise all values in both the column i and the line i in matrix E are replaced by 1. Those modification ensures that when algorithm stops, remaining components have the same dimensions.
Finally, we transpose matrices of all remaining components and use Algorithm 1 again. As a result we obtain image reflected with respect to the diagonal.
The implementation of the described technique is presented in following algorithm Input: Table M of images, number m of rows 1: mh := horizontal dimension of all Mi 2: r := lenght of M 3: mv := vertical dimension of all Mi 4: width := rmh
m 5: Creating the matrix E by executing of steps from 4 to 12 of the Algorithm 1. 6: while Length of M > m do 7: Executing of steps from 14 to 22 of the Algorithm
First example1 is basic. We have three strips. In first iteration the minimal error was found for M1 and M3, so we join first and third part. Now we have only 2 parts and we need to check in which way we should join them, so we need to check which erros is smaller, e21 or e12. e12 is smaller so we join the component M1 with M2.
The next example shows how the algorithm works to divide an image into rectangles. We have 12 rectangles: 200 100 px. Below we have the program start.
In first iteration the minimal error was found for M12 and M10, so we join 12th and 10th. As a result we have 11 1To test the algorithm were used random images from Google Images. parts. Next steps are similar. In each steps (I-VIII) we find the minimal error between all parts of the image and then we check the minimal error and join the corresponding parts of the the image.
The IXth step is another than earlier steps. We have to transpose the matrix to continue the procedure. Next, we will continue the previously described procedure, i.e. we will compare all parts and join those for which the error eij will be the smallest.
XII step (joining part 2 and 1)
The basic problem of algorithms is their working time. We can compare the operation of the program for division the image only veritcally or veritcally and horizontally. The time of the program does not depend on the degree of differentiation of the image, because each time we compare the same number of pixels (for a fixed image size and its division). The duration of the program depends on the number of compared pixels and kind of divising. Of course if the size of the image (number of pixels) is greater, then the working time is greater. The graph below shows the approximate running time of the program for diffrent divisions.
We see that the relationship between image size and time is linear for each division: for only vertically and for vertically and horizontally division.
VI. CONCLUSION
The "Puzzles" algorithm can be extended to cases when the divisions are irregular, i.e. the sizes of vertical and horizontal divisions are different. Currently, such a situation is impossible, because the algorithm requires equal divisions. In addition, it can be seen that combining images may be incorrect for situations where the images are very similar or specific. Since our algorithm finds first components with minimal error, join them and proceed to the next step, we might obtain wrong result if there were more components with the same error. For example when the majority of the image is one color.
Another problem is time of working. For large images divided in many components, it might take relativily a lot of time for algorithm to stop. It is caused by amount pixels needed for algorithm to compare.
Algorithms described above may have applications in decision support systems that search for objects with characteristic attributes. Our algorithms may be used for finding elements of images that fits the fixed pattern.