Solving a Rubik's Cube with computer vision
Jokinen, Lauri (2024)
Jokinen, Lauri
2024
Teknisten tieteiden kandidaattiohjelma - Bachelor's Programme in Engineering Sciences
Tekniikan ja luonnontieteiden tiedekunta - Faculty of Engineering and Natural Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2024-01-30
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202401221650
https://urn.fi/URN:NBN:fi:tuni-202401221650
Tiivistelmä
In this thesis, computer vision tools for solving the Rubik’s Cube are examined and developed. The main goal of the thesis is to develop a program that can detect the state of a scrambled Rubik’s Cube via webcam, compute a solution for it, and guide human user to execute the solution. This is done in Python using software libraries OpenCV for computer vision tasks and Kociemba for solution computing. Besides creating the program, the goal of this thesis is to examine commonly used tools and practices in the field of computer vision, and to present its applications on other fields of activity.
In the first part of the thesis, the relevant background information is presented for the reader. Structure and mechanics of the Rubik’s Cube are discussed, existing solving algorithms are compared to each other, uses and evolution of computer vision are examined, and three already existing remarkable robotic Rubik’s Cube solvers are presented.
In the second part of the thesis, the implementation of the program is discussed. The program is implemented using traditional computer vision techniques that are based on detecting different colors and shapes from an image following hard-coded rules rather than utilizing machine learning, although advanced techniques that take use of machine learning are briefly discussed in the background info section. To compute solutions for given states of the cube, an algorithm developed by German mathematician Herbert Kociemba is used. The algorithm allows the program to find near-optimal solutions in minimal time.
The programming process was demanding, and it took lots of debugging and error fixing to get the program to work in desired way. Biggest challenges turned out to be the changes in lighting conditions of the environment, and some specific patterns of the cube pieces that often led to flawed conclusions of the state of the cube. However, the final version of the program meets the goal of solving the Rubik’s Cube from any starting state and does not seem to be prone to errors when used properly.
A useful improvement for the program would be an automatic calibration of the limit values of the colors to get them to match the prevailing lighting conditions. Also, the detection features could be improved in a way that it would not be so strict in which order the user shows each face to the camera and how the cube is held during the detection and solving. The program could also be used in future applications where the human user would be replaced by robotic hardware handling the cube, making the system completely autonomous. Tässä työssä tutkitaan ja kehitetään konenäön työkaluja Rubikin kuution ratkaisemiseksi. Työn ensisijainen tavoite on luoda tietokoneohjelma, joka tunnistaa sekoitetun Rubikin kuution alkutilan verkkokameran välityksellä, etsii kyseiselle alkutilalle ratkaisun ja ohjeistaa ohjelman käyttäjää toteuttamaan tämän ratkaisun. Ohjelma toteutetaan Python-ohjelmointikielellä käyttäen hyväksi ohjelmistokirjastoja OpenCV ja Kociemba, joista ensin mainittua käytetään konenäön tehtävissä ja jälkimmäisenä mainittua kuution alkutilaan sopivan ratkaisun etsimisessä. Ohjelman toteuttamisen lisäksi työn tavoitteena on tutustua konenäön tehtävien parissa yleisesti käytettäviin työkaluihin ja toimintamalleihin sekä esitellä konenäön käyttökohteita eri toimialoilla.
Työn ensimmäisessä osassa lukijalle esitetään oleellista taustatietoa työn aiheeseen liittyen. Ensin käsitellään Rubikin kuution rakennetta ja mekaniikkaa, minkä jälkeen vertaillaan olemassa olevia ratkaisualgoritmeja keskenään. Sen jälkeen käydään läpi konenäön käyttökohteita ja sen historiallista kehitystä, ja lopuksi esitellään kolme kuuluisaa Rubikin kuution ratkaisemiseen suunniteltua robottia.
Työn toisessa vaiheessa käsitellään ohjelman toteutusta. Ohjelmassa hyödynnetään manuaalisesti koodattuja, perinteisiä, muotojen ja värien tunnistamiseen pohjautuvia konenäön tekniikoita kehittyneiden koneoppimismallien sijaan, joskin myös kehittyneempiä koneoppimista hyödyntäviä tekniikoita käsitellään pintapuolisesti työn ensimmäisessä osassa osana oleellisia taustatietoja. Kuution alkutilaa vastaavan ratkaisun etsimiseen käytetään saksalaisen matemaatikon Herbert Kociemban kehittämää algoritmia, joka mahdollistaa lähes optimaalisten ratkaisujen löytämisen minimaalisessa ajassa.
Ohjelmointiprosessi oli vaativa ja haluttujen toiminnallisuuksien saavuttaminen vaati runsaasti iteratiivista virheiden etsintää ja korjausta. Muuttuva valaistus ja tietyt hankalasti tunnistettavat kuution alkutilat osoittautuivat suurimmiksi haasteiksi. Vaikeuksista huolimatta, ohjelman lopullinen versio täyttää sille asetetut tavoitteet: kuutio saadaan ratkaistua mistä tahansa alkutilasta eikä ohjelma vaikuta olevan altis virhetilanteille, kun käyttäjä seuraa annettuja ohjeita.
Ohjelmaa voisi edelleen kehittää lisäämällä siihen automaattisen värien raja-arvojen kalibroinnin, joka sovittaisi raja-arvot vallitsevaan valaistukseen sopiviksi. Myös kuution tilan tunnistamista voitaisiin kehittää joustavampaan suuntaan siten, että käyttäjä voisi näyttää kuution sivut kameralle haluamassaan järjestyksessä ja pitäen kuutiota missä tahansa asennossa. Tulevaisuudessa ohjelmaa voitaisiin hyödyntää myös osana täysin autonomista robottia, jossa ihmiskäyttäjä olisi korvattu mekaanisilla osilla, jotka kääntelevät kuutiota ja sen sivuja ohjelman käskyjen perusteella.
In the first part of the thesis, the relevant background information is presented for the reader. Structure and mechanics of the Rubik’s Cube are discussed, existing solving algorithms are compared to each other, uses and evolution of computer vision are examined, and three already existing remarkable robotic Rubik’s Cube solvers are presented.
In the second part of the thesis, the implementation of the program is discussed. The program is implemented using traditional computer vision techniques that are based on detecting different colors and shapes from an image following hard-coded rules rather than utilizing machine learning, although advanced techniques that take use of machine learning are briefly discussed in the background info section. To compute solutions for given states of the cube, an algorithm developed by German mathematician Herbert Kociemba is used. The algorithm allows the program to find near-optimal solutions in minimal time.
The programming process was demanding, and it took lots of debugging and error fixing to get the program to work in desired way. Biggest challenges turned out to be the changes in lighting conditions of the environment, and some specific patterns of the cube pieces that often led to flawed conclusions of the state of the cube. However, the final version of the program meets the goal of solving the Rubik’s Cube from any starting state and does not seem to be prone to errors when used properly.
A useful improvement for the program would be an automatic calibration of the limit values of the colors to get them to match the prevailing lighting conditions. Also, the detection features could be improved in a way that it would not be so strict in which order the user shows each face to the camera and how the cube is held during the detection and solving. The program could also be used in future applications where the human user would be replaced by robotic hardware handling the cube, making the system completely autonomous.
Työn ensimmäisessä osassa lukijalle esitetään oleellista taustatietoa työn aiheeseen liittyen. Ensin käsitellään Rubikin kuution rakennetta ja mekaniikkaa, minkä jälkeen vertaillaan olemassa olevia ratkaisualgoritmeja keskenään. Sen jälkeen käydään läpi konenäön käyttökohteita ja sen historiallista kehitystä, ja lopuksi esitellään kolme kuuluisaa Rubikin kuution ratkaisemiseen suunniteltua robottia.
Työn toisessa vaiheessa käsitellään ohjelman toteutusta. Ohjelmassa hyödynnetään manuaalisesti koodattuja, perinteisiä, muotojen ja värien tunnistamiseen pohjautuvia konenäön tekniikoita kehittyneiden koneoppimismallien sijaan, joskin myös kehittyneempiä koneoppimista hyödyntäviä tekniikoita käsitellään pintapuolisesti työn ensimmäisessä osassa osana oleellisia taustatietoja. Kuution alkutilaa vastaavan ratkaisun etsimiseen käytetään saksalaisen matemaatikon Herbert Kociemban kehittämää algoritmia, joka mahdollistaa lähes optimaalisten ratkaisujen löytämisen minimaalisessa ajassa.
Ohjelmointiprosessi oli vaativa ja haluttujen toiminnallisuuksien saavuttaminen vaati runsaasti iteratiivista virheiden etsintää ja korjausta. Muuttuva valaistus ja tietyt hankalasti tunnistettavat kuution alkutilat osoittautuivat suurimmiksi haasteiksi. Vaikeuksista huolimatta, ohjelman lopullinen versio täyttää sille asetetut tavoitteet: kuutio saadaan ratkaistua mistä tahansa alkutilasta eikä ohjelma vaikuta olevan altis virhetilanteille, kun käyttäjä seuraa annettuja ohjeita.
Ohjelmaa voisi edelleen kehittää lisäämällä siihen automaattisen värien raja-arvojen kalibroinnin, joka sovittaisi raja-arvot vallitsevaan valaistukseen sopiviksi. Myös kuution tilan tunnistamista voitaisiin kehittää joustavampaan suuntaan siten, että käyttäjä voisi näyttää kuution sivut kameralle haluamassaan järjestyksessä ja pitäen kuutiota missä tahansa asennossa. Tulevaisuudessa ohjelmaa voitaisiin hyödyntää myös osana täysin autonomista robottia, jossa ihmiskäyttäjä olisi korvattu mekaanisilla osilla, jotka kääntelevät kuutiota ja sen sivuja ohjelman käskyjen perusteella.
Kokoelmat
- Kandidaatintutkielmat [8799]