Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

FEDERAL STATE AUTONOMOUS EDUCATIONAL INSTITUTION FOR HIGHER EDUCATION NATIONAL RESEARCH UNIVERSITY

«HIGHER SCHOOL OF ECONOMICS»

Faculty of Computer Science

Guiding Program for Assembling Rubik's Cube Based on 3D Model

Student

Nikita Kazachenko

Name, Surname

Moscow, 2019

Abstract

Rubik's Cube is the most famous toy in the world. It was invented by Erno Rubik more than 40 years ago and it is still very popular nowadays. The conception of the Rubik's Cube was not a toy at the beginning, but a practical geometry manual for the schools and universities. Also, it became the object of serious research by mathematicians, and later - the object of close attention for programmers.

Nowadays, this puzzle is still attracting the attention of many people around the world. Gratefully modern technologies it is possible to learn how to solve the Rubik's cube for anyone without hard learning the algorithms. Decision support systems could be a great assistance for any person who wants to get experience in solving. rubik algorithm computer application

This paper explores the possibility of using computer vision technology as a method of interaction with the user in the decision support system. The purpose of this work is to develop an application, which allows solving the Rubik's cube, initial configuration obtaining and interaction with the user goes through the smartphone front camera using computer vision technology and graphics.

To achieve the purpose of this work provided some investigations about existing solutions for computer vision technology implementing. A comparison between existing solving solutions was made and identified their advantages and disadvantages. To provide interaction with the user, developed algorithms, allowing creating a 3D model of real Rubik's cube using a smartphone camera. Developed methods for displaying the created 3D model displaying on the smartphone screen using the OpenGL library. Developed an algorithm for solving the Rubik's cube model and guiding the user through the steps to achieve the solution.

The paper result is a working Android application.

Аннотация

Кубик Рубика самая известная игрушка во всем мире. Она была изобретена Эрно Рубиком более 40 лет назад и до сих пор остается очень популярной. Изначально, концепция Кубика Рубика была не игрушкой, а практическим пособием по геометрии для школ и университетов. Также она стала объектом серьезных исследований математиков, а позже и объектом пристального внимания разработчиков.

В наши дни, эта головоломка до сих пор привлекает внимание многих людей по всему миру. Благодаря современным технологиям, любой может собрать Кубик Рубика, не прикладывая особых усилий по запоминанию сложных алгоритмов. Системы принятия решений могут оказать существенную помощь любому, кто хочет потренироваться в сборке кубика.

Эта работа исследует возможность использования технологии компьютерного зрения в системе принятия решений, в качестве метода взаимодействия с пользователем. Цель данной работы - разработка приложения, которое позволяет собирать Кубик Рубика, получая начальную конфигурацию и взаимодействуя с пользователем через фронтальную камеру смартфона, с использованием технологии компьютерного зрения и графики.

Для достижения заданной цели, были проведены исследования о существующих решениях для внедрения технологии компьютерного зрения. Было проведено сравнение между существующими системами, позволяющими собирать кубик, и выявлены их достоинства и недостатки. Для взаимодействия с пользователем разработаны алгоритмы, которые позволяют создавать трехмерную модель реального кубика, используя камеру смартфона. Затем на основе этой модели, были разработаны методы, позволяющие отображать созданную модель на экране устройства, используя библиотеку OpenGL. Разработан алгоритм для решения Кубика Рубика и показа пользователю необходимых действий для достижения результата.

Basic definitions, means, and abbreviations

Computer vision - is the transformation of data from a still or video camera into either a decision or a new representation. All such transformations are done for achieving some particular goal. A new representation might mean turning a color image into a grayscale image or removing camera motion from an image sequence.

Rubik's cube - is a 3D combination puzzle invented in 1974 by Erno Rubik. Consist of six faces and each has nine tiles. The structure of the cubelets enables each face to turn independently, mixing up the colors. It could be approximately at one of 43 quintillion permutations.

Tile - could have one of six Rubik's cube colors. Each Rubik's face contains nine tiles.

Cubie - a part of Rubik's cube. It could be a corner with three tiles on it, medium with two tiles or center, containing one tile. Each face has nine cubies; some of them are common for a few faces.

Permutation - the process of rearrangement of the pieces of the cube and it deals with orientation and position of pieces.

Decision support system (DSS) - computer-based application, which allows to collect, analyze data, present it to the user and contribute to making business decisions more effective and simple.

1. Introduction

Nowadays computer vision using in many areas of our life and people are using it on a daily basis. Computer vision is the area engaged in automated real-world images processing for extracting and interpreting information. This technology makes it possible for machines finding, tracking, classifying and identifying objects, extracting data from images and analyzing the received information. It is a large and growing range of applications for computer vision across many industries. [1]

It is hard to solve the Rubik's cube for most of the people. The main problem here is difficult to analyze text-written algorithms and use them. In this case, using a decision support system can be very helpful. The main purpose of a decision support system is collecting, analyzing and providing processed results for increasing the quality of decisions. Combining such a system with computer vision technology for a more convenient way of data collecting can be a powerful tool for more effective teaching people, in this case, Rubik's cube solving.

Using computer vision technology makes it is possible to obtain user movements and check if they are correct very quickly, while he is holding the real cube. Besides CV, muscle memory is also using in this work, cause the user repeats the solving steps to achieve the solution.

Research object - 3D model visualization system with DSS features, interacting with the user through the computer vision technology.

Research subject - methods and algorithms for 3D-reconstruction of objects, visualizing 3D-objects, algorithms for pattern recognition, Rubik's cube solving algorithms, using computer vision technology in decision support systems.

Goal - develop an application, which allows solving the Rubik's cube, initial configuration obtaining and interaction with user goes through the smartphone front camera using computer vision technology and graphics.

To clarify the scope of the study, it is necessary to fulfill several tasks:

1) Compare existing solutions for solving the Rubik's Cube, find its advantages and disadvantages.

2) Define the main application functions, required for DSS.

3) Create an appropriate Rubik's cube model, using data about its structure, notations and solving algorithms.

4) Create an algorithm, which allows performing the Rubik's cube scanning process.

5) Develop an algorithm, allowing creating a 3D model of real Rubik's cube, using computer vision technology.

6) Create a graphics drawing system, required for interaction with the user and displaying the 3D model.

7) Create a method for solving the generated 3D model.

8) Develop an algorithm, required for guiding the user through steps to solve the Rubik's cube.

9) Develop a user-friendly interface.

2. Subject description

2.1 Rubik's Cube

This chapter contains a description of Rubik's cube model parts, how they can be represented, the mathematics background behind this puzzle and different notations, using for denoting the sequences of turns. All the discussed information is required in the application development process.

2.1.1 Rubik's Cube 3D model

The Rubik's cube contains six faces, each of them has a unique color, such as: white, green, yellow, orange, red and blue. The model of the cube, using in this thesis is: green is the opposite to blue, orange is opposite to red, and yellow is opposite to white. The face consists of nine tiles, the smallest part of the cube (Figure 2). In addition, the cube is represented as 27 cubies, which can be corner, edge, and center. Corner cubie consists of three tiles, edge of two and center of one tile. There is one more structure, used in this work, which is called layer (Figure 1). Layer consist of nine cubies and each layer has names: left, right, back, front, up, down, middle, equator, and standing.

Figure 1. Layer of the CubeFigure 2. Face of the Cube.

Rubik's cube is a permutation group in terms of mathematics. It has six different colors, each of them is repeated 9 times, hence it can be represented as a list consist of 54 elements with numbers from 1 to 6. It is possible to rotate 6 layers of the cube to determine 6 basic permutations, which reform the list in particular way. A Permutation is a sequence of 0 or more of these basic moves. In other words, these 6 moves define a group (G) of all moves. [4]

· Associative - the permutations can be sorted together, for example (L'U)R = L'(UR)

· Neutral element - there are permutations, which does not reform the selection, for example, LL'

· Inverse element - there is an inverse move to permutation, for example, L - L'

· Degree of permutations - number, which represents how many permutations are necessary for returning to the initial cube state.

The number of possible permutations of the tiles on the Rubik's cube is huge. 8 corner cubies can be adjusted in 8! ways and each can be arranged in 3 directions, which give us 3^8 variants for each permutation of the corner cubie. There are 12! ways to adjust 12 edge cubies. Edge cubie has 2 possible orientations, due to each permutation of edge cubies has 2^12 arrangements. However, in the Rubik's cube, only 1 of 3 permutations has the right rotation of the corner cubies. Only 1 of 2 possible permutations have the same edge-flipping orientation as the original cube, and only 1 of these have the correct cubie-rearrangement parity. This gives = 4.3252*possible configurations. [3]

The configuration of the Rubik's cube depends on not only the positions of the cubies but also on the orientation of the cubies, therefore this fact,not every cube configuration if solvable. There is a chance that cube will be unsolvable, if scramble the cube and solve it back.

To convey the information about a particular turn or a sequence of turns of the Rubik's Cube it is very helpful to use notations. There are many variations to mark parts of the Rubik's Cube. To denote sequences of moves in this work used notations developed by an English professor of mathematics David Singmaster.

Sing master notation implies F (Front) side of the cube is facing to the user, and other sides mark as L (Left), R (Right), B (Back), U (Up), D (Down). Clockwise quarter turn layer rotations denote the same way as cube sides. For counterclockwise quarter turn layer rotation, it is necessary to add a ` symbol, for example,R'. Appending a 2 to one of the side letters means a half turn layer rotation, but this notation is not used in this work to simplify the user experience. [2]

There are also notations for the entire cube rotation. X notation represents 90 degrees rotation around the X-axis or R turn and X' - R' turn. Y notation means 90 degrees cube rotation around Y-axis or U-turn. Z notation denotes a 90 degrees rotation around Z-axis or F turn. Often these moves are also represented as a sequence of three primitive moves.

2.1.2 Rubik's Cube solving algorithms

There are many algorithms for Rubik's cube solving, which can be divided into two groups: for human solving and for machine solving. There are three popular algorithms for human solving.

The first one is the most popular algorithm called the Fridrich method (CFOP). It was developed Czech speedcuber Jessica Fridrich in 1980. The method consists of four steps and works on a layer-by-layer system. Firstly it is necessary to make a cross on the bottom side of the cube. After that solve the first two layers, other words pair up corner and edge tiles and move them to the correct location (F2L), locate the last layer for making the upside of the cube filled (OLL) and permute the last layer to finish solving (PLL). CFOP is very popular among the speedcubers for its dependency on the algorithms, muscle memory, and pattern recognition, as opposed to other more intuitive methods. [10]

Roux methodwas developed by French speedcuber Gilles Roux. It is similar to the Petrus method in using block building but has its own features. Firstly, it is necessary to solve the 1x2x3 block on one side of the cube, and on another later. Thereafter last layer corners are orienting using CMLL. On the next step, the wrong edges are orienting. After that, it is necessary to solve the two edges which belong above the 1x2x3 blocks. To finish the solving final four edges are permuting. Roux method uses fewer moves, algorithms and more intuitive, than Fridrich method. But for beginners, it could be too difficult building the block of cubies. It is not so popular among the speedcubers due to widely using M turns, which is not easy to make every time.

Kociemba's algorithm is a computer method developed by Herbert Kociemba. It is an improved version of Thistleth waite's algorithm. On the first step of this algorithm it is necessary to get the cube in particular state “G1” with such properties:

1. Every cornerisoriented

2. Every edgeisoriented

3. Middle layer edges positioned on the middle layer

From “G1” state it is possible to apply <U, D, F2, B2, R2, L2> for cube solving, and it also means that elements within up and down layer can not move out of the two layers.

It was proven in 2010 by Herbert Kociemba, Tomas Rokicki, Morley Davidson, and John Dethridge, using Google supercomputer, that 20 moves are enough to solve the Rubik's cube from any configuration. This number is called God's number and Kociemba's algorithm allows solving the cube for not more than 20 moves.

It was decided to use the realization of the Fridrich solving method in this work, due to its popularity and simplicity for newbie users. In addition, some modifications were made in this algorithm, during the development process, to make solving phases smaller and understandable.

2.1.3 Hardware and software systems for Rubik's Cube solving

Throughout the history of the Rubik's cube, there were many systems created for solving it. These systems have different features and work principles. Some of the systems will be described below.

CubeX. Android application for solving the cube. It is possible to generate the shortest possible solution from any initial configuration. Has the ability to scan the cube state using a camera or enter it manually. There are two solving mechanisms: the Fridrich method and Kociemba's Two-Phase algorithm. The user interface of the app is shown in Figure 3. This application is available in Play Market with the reference:

https://play.google.com/store/apps/details?id=diozz.cubex

The application also has some drawbacks. The first one, it is hard to keep up with 3D Rubik's cube model during the solving process and realize if a mistake was made if the user is rookie. The second drawback is recognition difficulty; it is not comfortable to hold the cube in one hand and the smartphone in another during this process. In addition, there is a possibility of incorrect recognition.

Figure 3. The interface of the CubeX app.

Solving robot. There are many existing robots for solving the Rubik's cube. The last world record solving time is 0.38 seconds and achieved in 2019 by MIT students Ben Katz and Jared Di Carlo. “They set up a motor actuating within each face of the Rubik's cube controlled by electronics for control. With the assistance of webcams pointed at the cube, custom software determines the initial state of each face. Then, utilizing pre-existing software to solve the Rubik's Cube, the robot was guided to solve the puzzle.” [11] It is a huge achievement and it is impossible for any human to beat it. Unfortunately, this solving algorithm and robot are not applicable for daily using.

Smart Rubik's cube. This year few companies released a “reinvented” Rubik's cube. The main feature of it is the ability to connect to the smartphone through bluetooth. Smart cube is designed to track and estimate user movements, teach and guide the user for solving achievement. These functions are achieved, using smart sensors in the cube, which allows obtaining current configuration instantly. In addition to the cube, companies offer an application, which allows interacting with the cube. [12] The application includes different tutorials, modes, and leaderboards for competing with players around the world (Figure 4).

Figure 4. Smart cube.

Smart cube inventing is a really great achievement, but the main drawback here is price, which is around 100 dollars.

Reviewed solving systems have many accomplishments. Due to the fact they have some disadvantages, it was decided to develop own solving system, tacking the first reviewed application was taken as the basis for this work, considering all the advantages of it. To improve the working process, added features, such as: using computer vision as an interaction method with the user, using smartphone front camera, instead of back, used in CubeX, and using another solving algorithm, which is simpler for a newbie user.

2.2 Computer vision

Computer vision is an artificial intelligence area, robotics in particular, and related with its technologies for real-world objects obtaining, processing and using received data for solving various kinds of applied problems without the participation of a person. The scheme of the computer vision working principleis shown in Figure 5.

The main goal of computer vision is to understand the content of digital images. Usually, this involves developing methods that try to reproduce the capability of human vision.

Understanding the content of digital images may involve extracting a description from the image, which may be an object, a text description, a three-dimensional model, and so on.

Thanks to the development of deep machine learning, neural networks, and artificial intelligence, great discoveries have occurred in this area and computer vision has been able to exceed people in some tasks. To create a deep learning algorithm, it is necessary to collect a large amount of training data and adjust parameters, such as epochs of training and layers of neural networks. However, computer vision has difficulty understanding the relationship between objects and the context of the images they observe. For the algorithm, the image is an array of colored pixels that can be matched with descriptions. It is believed, that true computer vision can be achieved only if artificial intelligence is created.



Figure 5. Computer vision in image processing.

Computer vision progresses really fast, due to cheaper and more powerful cameras and because processing algorithms are starting to mature. It is one of the core technologies by which the digital world can interact with the real world.

Computer vision plays a significant role in this project. Using this technology in the projectmakes it possible to solve the task, defined in the introduction, related to the interaction with the user using a smartphone front camera. Due to this factor, some of the methods, which have been using in developing, will be discussed below. [1]

2.2.1 Gaussian filter

Any process related to image processing, cannot start without reducing image noises. Many methods are allowing reducing image noises and blur image, but most of them are the variations of the most well known and performance is the Gaussian blur method. Due to this factor, it was chosen for this work.

The Gaussian-smoothing operator is a 2D convolution operator that is used to remove noises from images and blur them. It is necessary to reduce image noises to increase detection quality. Gaussian filter applying to convolve with the image for smoothing it. Gaussian filter kernel having size (2k+1)Ч(2k+1) has the equation:



Where у is the standard deviation of the Gaussian distribution, k is the weight of Gaussian kernel, j and i represent the pixel position in the image.

Below you can see an example of a 5x5 Gaussian filter, required for creating a neighbor image, with у = 1.4.

Figure 6. Gaussian blurring.

Detector performance depends on the size of the Gaussian kernel. Kernel coefficients represented by the formula below, where у is a standard deviation of the distribution. Supposed the distribution mean is zero.

Here is the formula of Gaussian blurring for two dimensions:



Wherex is the distance from the origin in the horizontal axis, y is the distance from the origin in the vertical axis, and у is the standard deviation of the Gaussian distribution.

The result of applying the Gaussian filter to the image is in Figure 6. To reach this result it is necessary to multiply each pixel of the image to the kernel. After that, the obtained values add up and the result becomes the value at the destination pixel. The algorithm result is a "weighted average" of each pixel adjacency and the central pixels have a bigger average weight. This is in contrast to the mean filter's uniformly weighted average. Because of this, a Gaussian provides gentler smoothing and preserves edges better than a similarly sized mean filter. [5]

2.2.2 Canny edge detector

The next step after reducing image noises is finding the object contours. It is necessary for determining the location of Rubik's cube tiles. For this task chosen Canny edge detector operator, because other detectors that have better performance, usually require more parameters and have longer computation times.

Canny edge detector operator created in 1986, by John F. Canny. This detector uses a multi-stage algorithm to detect a wide range of borders in images. Although the developing process was carried out at the dawn of computer vision, Canny's edge detector is still one of the best detectors. It is difficult to find a detector that would work much better, than a Canny detector.

The algorithm is not limited by calculating the gradient of a smoothed image. Only the maximum points of the image gradient are left in the edge contour, and not the maximum points lying near the border are deleted. It also uses information about the direction of the border in order to remove points just next to the border and not to break the border itself near the local maximums of the gradient. Then, using two thresholds, weak boundaries are removed. A fragment of the border is processed as a whole. If there is a gradient value on the tracked fragment, which exceeds the upper threshold, then this fragment also remains permissible edge in those places where the gradient value falls below this threshold until it falls below the lower threshold. If there is no single point with a value greater than the upper threshold on the whole fragment, then it is removed. [15]

The main stages of the algorithm:

1. Smoothing. Blur image to remove noise.

2. Searching the intensity gradients. Edges are marked where the image gradient takes the maximum value. They can have different directions, so the Cannyalgorithm uses four filters to detect horizontal, vertical, and diagonal edges in a blurry image.

3. Non-maximum suppression. Only local maxima mark as edges.

4. Double threshold. Thresholds determine potential edges.

5. The resulting edges are determined by suppressing all edges that are not associated with certain strong boundaries.

Figure 7. Applyinga Canny edge detector.

Using aCanny edge detector in this work was the right choice. It provides high detection speed and clear contours, required for further processing. Applying the detector to the cube is shown in Figure 7.

2.2.3 Dilation method

Obtained contours on the previous step are thin and intermittent. To make it possible finding rectangles on the image, it is necessary to increase the width of the lines and remove spaces between them. For such purposes, there are morphology operators in OpenCV. In this case, the desired function is dilation.

The dilation process purpose is reducing the holes enclosed in one area and making the distance between the gaps lower. Two parts of the data are necessary for this process. The first one is an image, which is going to be dilated. The second one is a structuring element or a kernel. This element determines the impact of the dilation on the image.

It is necessary to consider each background pixel from the image, to compute the dilation. The kernel superposes on each background pixel, so the starting point of the kernel matches with the pixel position. If there is a pixel in the kernel matches with a foreground pixel, hence the input pixel becomes equal to the foreground value. [6]

If all the corresponding pixels in the image are background, however, the input pixel is left at the background value, but if all the pixels in the image are background, the input pixel does not change. It is possible to get the result as is in Figure 8, after applying dilation.



Figure 8. Image with applied dilation.

2.2.4 Contrast Limited Adaptive Histogram Equalization

There are some changes in the scanning process, since course work defense. One of these changes is using adaptive histogram equalization. This technique enhances the contrast in images, and thanks to this factor, tiles detection in excess or low light conditions were improved.

Adaptive Histogram Equalization (AHE) is used for improving contrast in images. During performing AHE, if the processing area has a small intensity range, then the noise becomes more notable. Due to this process, some artifacts may appear. To reduce the number of possible noises and artifacts, developed a modification to AHE, called Contrast Limited AHE. [8]

CLAHE added a limit to get over the noise intensification problem. It solves the problem by clipping the histogram at a predetermined value and after that computes the cumulative distribution function (CDF). There are two main parameters: the clip limit and block size. Image quality determines by these two parameters. Increasing the clip limit makes the histogram plainer and the image becomes brighter. Image contrast depends on the block size parameter. Histogram equalization applies to every context area, original histogram clipping and the pixels reallocate to the gray levels.

Figure 9. Original image. Figure 10. Applied CLAHE.

There is a difference between the two diagrams because each pixel intensity bounded a particular maximum. However, minimum and maximum gray value is the same on both images.

CLAHE algorithm consists of these steps:

1. Split up the original image into non-overlapping context areas.

2. Using gray levels in the array image, compute the histogram for each related context area.

3. Compute the histogram of the context area by CL value.

4. Reallocate remained pixels until all the pixels reallocated.

5. Using Rayleigh transform to increase the intensity values in every context area. Derived histogram transforms to cumulative probability, necessary for creating transfer function.

6. Reducing the harshly changing effect.

7. In order to remove the boundary artifacts, it is necessary to compute the new gray level of pixels into a sub-matrix context area applying a bi-linear interpolation among four various mappings. [7]

There are examples of applying the CLAHE in Figure 10, and in Figure 9 shown picture without applying this filter.

Second chapter summary

The second chapter contains information about computer vision technology and the main image processing functions, used in this work. Based on tasks 1, 2, 3 and 4, defined in the introduction, researches were made. For solving tasks 1 and 2, compared existing Rubik's cube solving systems, identified and took into account their main advantages and disadvantages. It was decided to use the smartphone front camera and computer vision technology for interaction with the user.

Provided the description of Rubik's cube model and methods of interaction with it. This information was helpful in developing the 3D model of the Rubik's cube and allowed to solve task 3.

Previously in the coursework, was provided a comparison between computer vision libraries, and the OpenCV library was chosen as an appropriate one. In this chapter described computer vision methods, which used for solving task 4, their principals of work and examples of applying them in the real application.

In addition, this chapter contains information about different algorithms for Rubik's cube solving and their comparison. After all, the Fridrich solving method was chosen as an appropriate one, due to its simplicity for newbie users.

3. Designing and developing application for assembling a Rubik's Cube

The application designing process started with choosing the platform for the application. Due to the fact, application should be for smartphones and because of having experience in Java language, chosen Android platform. The coursework was developed on Java language, but it has some disadvantages, for example not very comfortable working with lambda expressions and threads. That is why, it was decided to use Kotlin language in this work and after all, seems it was the right choice. It is neater, comparing to Java language and it is fully compatible with Java language, so it was not too hard to change most of coursework application parts into Kotlin language.

When the development platform and language were chosen, it was necessary to find the appropriate libraries for graphics drawing and computer vision functions using. There are no many computer vision libraries for Android, and most of them are not free. So it was decided to use theOpenCV library in this work. It is quite easy to use and it is the most popular computer vision library in the world. For graphics drawing on the Android platform using the OpenGL library. It is a native Android library and other libraries are just modified OpenGL. So it was decided to take the native library for graphics, despite the fact it has some disadvantages, found during the development process.

Figure 11. Starting screen of the application.

During the designing process created an application-starting screen, showing the buttons, leading to the main parts of the application. (Figure 11)

This chapter contains information about the designing and development process features.

3.1 Calibration mode

To make it possible using different Rubik's cube for solving, it is necessary to create setting color method, which would allow associate program colors with colors on the real cube. The colors also depend on light, and in conditions with different luminosity, tracking colors may differ. Due to these factors, it was necessary to make it possible for personal setting color tracking options for every user. A calibration function was developed and implemented to solve this problem.

The algorithm goes through all six cube's colors, showing the front camera image and the user should tap on the area with the necessary color. After each step of the algorithm, color extracts from the chosen area and writes to the shared preferences to have the ability to use calibrated colors in the future.

Figure 12. Screenshot of the calibration mode.

The process of calibration is shown in Figure 12. [1] On the top of the screen appears an indication, which says on what color on the cube user should tap at this moment. After all six colors are configured, the user should tap on the screen again to start the scanning process.

3.2 Scanning process

It is necessary to find the Rubik's cube tiles location for 3D model generation. For this purpose developed algorithm, which allows finding the contours of each tile for obtaining its color later. This algorithm was created using theOpenCV library.

First,it is necessary to convert the image to the grayscale. After that,it is possible to evaluate the brightness of the image and correct gamma in case the image is too dark for detection. [16]

Besides,an image could have flares, which disturb the detection process. To remove the flares used CLAHE algorithm, which means Contrast Limited Adaptive Histogram Equalization. The main purpose of this algorithm is increasing image global contrast. Through this adjustment, intensions can be better distributed on the histogram. It is very useful for images, which are too bright or dark, like in our case with Rubik's cube, due to lack of light on the downside of the cube. The general histogram equalization formula is:

[1]

whereis the minimum non-zero value of the cumulative distribution function, is showing that the minimum value in the subimage is 52 and the maximum value is 154, M Ч N represents the number of pixels in the image and L is the number of grey levels used, often takes as 256.

The result images after applying histogram equalization (see Figure 9 and Figure 10).

3.3 Color detection algorithm

An important part of the application is a color detection algorithm. It allows getting the color of each scanned rectangle. At the beginning of the algorithm, it takes a central part of the tile; it is possible due to obtained rectangle coordinates on the previous step. After that calculates the color of this part in HSV format. As the calibration process finished, we have values with which current measurements would be comparing. Using the color difference formula, discussed in the second chapter, calculates the color difference for each Rubik's cube color. After that it is possible to define tile color, its color difference would be minimal. The result of the algorithm working is a sorted list with tile colors, which will be using to draw the cube. [1]

val r = (measuredColor[0] +

candidateColorTile.hsvCalibrateValue!!.`val`[0]) / 2.0error = ((2 + r / 256.0) * (measuredColor[0] - candidateColorTile.hsvCalibrateValue!!.`val`[0]).pow(2.0) + 4 * (measuredColor[1] - candidateColorTile.hsvCalibrateValue!!

.`val`[1]).pow(2.0) + (2 + (255 - r) / 256.0) *

(measuredColor[2] - candidateColorTile.hsvCalibrateValue!!

.`val`[2]).pow(2.0))error = sqrt(error)

Above code shows the realization of the formula for color distance calculation, which is shownbellow. The measured color parameter in the code is the value, obtained from camera, and candidate color values take from shared preferences, after calibration process has been done.



The formula above allows computing the error ДCbetween each color component and determines how close these two comparing colors to each other.C in the formula means the value of red, blue or green color.

There are many color distance formulas, which try to use color spaces, such as HSV, with a hue in the form of a circle, placing different colors in the three-dimensional space of either a cylinder. However, most of them are just variations of RGB disregarding the di?erences in human color perception. [17]

3.4 Rubik's Cube structure model

There are few significant parts of the cube, which used for model drawing, scanning process and solving algorithm. (Figure 13)

1. Drawing model parts are a vertex, tile, cubie, layer and cube.

Vertex is simply the point in 3D space and each tile has four vertices.

Tile is the smallest part of the cube, which has four coordinates, represented by vertices, color and direction, represented by a normal vector. In addition, tiles with color, different from black, are visible for the user and called active tiles.



Figure 13. Parts of the Rubik's cube

There are three types of cubies in the Rubik's cube. Center cubie has one active tile and five inactive tiles, edge cubie has two active tiles and four inactive, corner cubie has three active tiles and three inactive. Each cubie contains a lot of information about its position in space and data for rendering.

The next element is the layer. There are nine layers in the Rubik's cube, such as front, left, right, back, up, down, middle, equator, standing. Each layer contains references to the cubies, direction and center point in 2D space. After every layer rotation, the cubie position is changing, so it is necessary to calculate a new position and determine which layers will contain this cubie using a center point for computation.

Cube is the main part of the model, which contains all the information about layers and cubies. It contains the primary cubies array, from which layers obtain references for local values.

2. The scanning model is necessary for storing scanned values. It consists of a tile and a cube face. Tile has color, obtained through the color detection algorithm, and coordinates in space, required for the tiles layout algorithm. The face has two arrays of tiles, using for color detection and information about tiles layout.

3. The solving model creates after the scanning process and represents a copy of the drawing model with modified and additional functions, required for solving step calculation.

3.5 Сalculatinguns canned cube elements

It is possible to determine the tile color incorrectly, during the scanning process. To reduce the possibility of this and reduce the computational load, decided to develop the algorithm, which will compute unscanned tile colors, using the scanned values.

Missed tiles on the Rubik's cubecould be calculated if a known minimum amount of other colors. For example, if the current cubie is center, its color is blue and it is on the up layer, then center cubie on the down layer has a green color, due to center cubies are not moving and we can definitely say what color is missed. It's not so easy to say with the edge and corner cubies, cause their location is absolutely random. The only possible way to determine missed color is to observe three cubies, containing missed color. For this purpose, it's necessary to take three cubies, with filled colors and find the missed color, cause each color on the cube has the opposite color. After finding the color, it will be set to the cubie and when the scanning process will process related face, this cubie would not be processed.

Figure 14. Calculating unscanned tiles.

The example of this process is shownin Figure 13. 3D model is almost created, it is necessary to scan the last side of the cube to finish it, but the algorithm calculated all possible tiles before scanning and after that, there are only two unscanned tiles (gray color in Figure 14).

Applying this author's algorithm in the work allows decreasing a computational error by around 10 percent and it reduces the time for tile color recognizing because most of the tiles are computed preliminarily. Besides, it is more comfortable for the user not to make additional rotating movement and obtaining the created 3D model faster.

3.6 Rubik's Cube 3D model rendering

To draw graphics application uses the OpenGL ES tool. The OpenGL ES APIs provided by the Android framework offers a set of tools for displaying high-end, animated graphics that are limited only by your imagination and can also benefit from the acceleration of graphics processing units (GPUs) provided on many Android devices. [13, 15] Typical path to drawing a square is to use two triangles are drawn together, which is shown in Figure 16.

Also, it is necessary to define the vertices in a counterclockwise order for both triangles that represent this shape and put the values in a ByteBuffer. Therefore, if we are going to draw tiles on each face of the cube, we should define each vertex of the tile or write it by yourself. To solve this problem, the developed algorithm, which computes each point on the tile using vertices coordinates of the whole cube, see Figure 16.

Going through all faces of the cube, which has coordinates as shown in Figure 15, the algorithm creates a dictionary where the key is face name and values are tiles with computed coordinates. [14]After this step, it is possible to combine different tiles to the cubies.



Figure 15. Vertices coordinates determined at the start of the application.

Figure 16. Drawing a square using two triangles.

Cubies are an important part of the cube because they make it possible to rotate the cube face. There are three types of cubies: corner, middle, and center. Corner cubies form using three tiles from different faces. Edge cubies have two tiles and center cubies have one tile.

3.7 Realization of Friedrich Rubik's Cube solving method

There are a lot of solving algorithms, as it was discussed in the second chapter, and not all the algorithms are applicable for humans. Due to the reason, this application should teach and help users to solve the Rubik's cube, the most popular and easy algorithm for human solving was chosen. The method is called CFOP (Cross, F2L, OLL, PLL), also known as theFridrich method.

The main steps of the algorithm are:

1) Cross - make a cross on one side using edges of a face and align the edges with the second layer.

2) First two layers - fill in the four slots between the cross pieces, one slot at a time. Each slot is filled by inserting a corner and its corresponding edge simultaneously. The completion of this step leaves one with just the last layer, typically placed on top. [9]

3) The orientation of the Last Layer - make the top layer of the cube a solid color.

4) Permutation of the last layer - finish solving the cube by permuting the top layer.

To make it more clearly and better perception, described steps were splitinto more parts, such asa white cross, white layer, two layers, yellow cross, yellow edges, yellow corners orientation and solving the yellow corners.

The solving process starts after the whole cube model is created usingthe scanning algorithm. The current drawing model copying to the abstract model, which represents a clone of the model and all the computations are performing insensibly for the user. After each layer rotation, abstract model updates and it is ready for the new permutation. If the current abstract model state has reached the solution of any solving steps, the data with guiding steps delivers to the class, which is responsible for interaction with the user. This class is showing the current move from obtained data, waiting for the user movement and after that checks if user movement was right.



Figure 17. Schema of the solving algorithm.

It is possible for the user to see the solving schema during application work, for this purpose, the user can press the “Show schema” button and determine which step he is. (Figure 17)

3.8 Preventing wrong moves algorithm

Due to the fact, the developed application has some features of the decision support system, as it was discussed in the second chapter, it was necessary to create a function for guiding the user through the steps and prevent him from making mistakes during the solving process. To solve this issue developed an algorithm, which allows checking when the user makes a wrong move, notify him about the mistake and guide him to the right path.

This algorithm is working due to the abstract model, which is solving the cube in the background process. It allows having a necessary cube configuration on each step of the solution and compares the user moves with the model. For comparing obtained data with the necessary configuration used a method, described in my course work.

Firstly, this algorithm comparing the center tiles. If their colors are not the same, taking two more tiles and compare them. Due to this operation, it is possible to unambiguously determine whether this face was added.The idea of the algorithm is to compare scanned tiles consistently with created tiles. It allows verifying user goes the wrong way and notifying him about that. [1]

Figure 18. Notifying about a wrong move.

As the result, the developed algorithm is notifying the user of an incorrect action by displaying an inscription that it is necessary to go back and perform the correct move, as well as showing a rotating arrow in the desired direction (Figure 18).

3.9 Solving speed training mode

For including an entertainment element in the solving process, the ability to turn on the auto cube assembly mode was added. This feature makes it possible to use another mode of solving the cube when the user should repeat rotation moves for the 3D model. This mode can be used for increasing the user's solving Rubik's Cube speed, by training making fast rotation moves, while repeating for the 3D model moves. For turning on this mode, added the “Play” button on the right side of the screen. The user can start it after one of the phases is computed and he obtained the guiding steps.



Figure 19. Auto-solvingbutton.

Also, it is possible to turn it on during the solving process and set the comfortable rotation speed. When this mode is turned on,the user can pause it and continue to solve the cube in regular way.

It is possible to use this mode for increasing the solving speed, by repeating necessary moves for the 3D model (Figure 19).

Figure 20. Solving process is finished.

When the solving process is finished, user can see the phrase with congratulation on the top of the screen and the indicator, notifying about the finish, on the left side(see Figure 20). After the Rubik's Cube is solved, user can rotate created 3D model to check that all tiles are on the right places and start the solving process again or close the application.

3.9 Application diagrams

To understand how the developed application works and what decision paths should user lead during the working process, used activity diagrams. The working process of the developed application was divided into two tasks.

The first one is the scanning process (Figure 21). The goal of this process is creating a 3D model of the Rubik's cube. The result of this process is the 3D model of the Rubik's Cube, created using obtained data from a smartphone front camera.

Figure 21. Activity diagram showing the flow of events in the application.

The second one is the solving process (Figure 22). Using the created 3D model of the Rubik's cube, from the previous task, the application starts to compute the guiding steps to achieve the solution of each of 7 phases. After the current phase is computed, the algorithm begins to observe the user movements for preventing the wrong moves. After reaching the end of the phase, the algorithm starts to compute the next phase.

Figure 22. Activity diagram showing solving the cube.

To demonstrate the structure and relationship between all objects in the developed system used a class diagram.

On the Figure 23 are shown application classes. These classes have different purposes. Every class will be discussed below.

Figure 23. Class diagram of the application.

StartupActivity - startup class with application logo and main buttons.

MainActivity- contains general information and settings.

RectanglesLayout- working with rectangles, a layout created shapes in the correct places on the matrix.

ImageRecognizer- class responsible for the scanning process and image processing.

Calibration - allows providing a calibration process.

CurrentState- tracks the number of processed cube faces.

Renderer - main class for drawing graphics in the application.

Arrow- allows drawing arrows, which show the direction of rotation for the user.

RubikTile- represents a tile of the Rubik's cube. It contains color, rectangle, state,and other information.

ColorDetector- the main function is determining the color of each face's tile.

ICubieInterface - describe the common features and functions of cubie and logic cubie.

ILayerInterface - describe the common features and functions for the layer and logic layer.

ICubeInterface - describe the common features and functions for cube and logic cube.

Cubie - contains information about the layout, animation, and graphics. It could be a center cubie, edge cubie, and corner cubie. Computes layout after rotation.

LogicCubie - a clone of cubie, but does not have graphics information. Used in the solving algorithm.

Layer - perform an interaction with cubies, rearrange cubies array after rotation, have graphics information.

LogicLayer - a clone of layer, but does not have graphics information, using for solving.

Cube - main class, which represents a 3D cube model, contains processing, drawing methods and interaction with parts of the cube, such as tiles, cubies, layers.

LogicCube - has information and methods for solvingthe process.

DirectionsControl - class responsible for computing current cube's sides colors, for example, if the cube was rotated, each side of it now has different colors.

Third chapter summary

The third chapter contains information about the application designing and development process. Shown what soft and hardware used for developing.

All the tasks defined in the introduction were solved. For task 5 developed algorithm, which allows creating 3D Rubik's cube model using data from a smartphone camera and OpenCV library for computer vision. Also, developedthe author's algorithm for computing the unscanned cube tiles, which helpedto improve recognition accuracy and computational loading. To solve the task 6, chosen OpenGL library, using its functions, 3D model and information for guiding user were drawn. Created a user-friendly interface and application design.

Solving the created 3D model of the Rubik's Cube, provided a unique realization of Friedrich solving method and added additional phases for better understanding by newbie users.

To solve task eight provided methods for guiding the user through the steps to achieve the solution. Necessary movements are showing to the user by arrows, directed into a particular direction. For having some features of the decision support system, created an algorithm, which notifies the user about wrong moves and shows what should be done for returning inthe right way.

...