Saturday, 18 February 2017

Rubik's Cube recognition part of MacTwist

Rubik's Cube recognition part of MacTwist

Following on from first post on how the MacTwist Rubik's Cube solver works. This post is about the second program we wrote, it is for recognize the cube and detect the colors.

This code was written in Python using OpenCV and the code can be found here

The first part of MacTwist was written in Small Basic and used the EV3 API to turn the lego motors using 2 EV3 bricks networked (daisy chained)  together. My original intention was to use a pixy camera to detect the colors as it will work on the lego brick and the image processing and recognition is done on board on the camera so I expected a plug and play setup see  . What I discovered is that when using pixy camera is it is really designed for object tracking rather than color detection, i.e it has not so accurate detection but can do it really fast so that a moving object can be tracked. With the lego brick it can only track 1 object at a time because the lego brick isn't fast enough to track multi object at 50FPS. I decided to buy a Raspberry Pi as it was much faster and would handle tracking multi object at a time. What I discovered was thta the pixy was to sensitive to different lighting condition and couldn't tell the difference between Orange and Red and couldn't detect white tiles either becuase it tracks hue and white doesn't have any Hue.

So now back to the drawing board. I decided to get a Pi camera for the Pi and try to write a program to detect the colors myself. As this was part of a project all about teaching my son to program I though this would be a good opportunity to take the next step and change to a lower language, after a bit of research it seemed that Python should go hand in hand with the Linux system.

After some googling it seemed the most common and recommended way to do what I wanted to do was with OpenCV (open source computer vision) . I set about learning how to progam in Python and how to down load OpenCV.

Getting started on the code

Problem 1: It wasn't that hard to get something that worked OK in recognizing the cube but what kept being the biggest problem was the different lighting from daytime to night time.

Problem 2: Although it worked OK it wasn't working perfectly so what I would do is work out ways to processing the image further to weed out the problems but image processing is very hungry and the little Pi has limited computing power compared to a PC and it didn't take much processing before the Pi couldn't do it in real time on a live stream.

I reduced the first problem by adjusting the brightness of the camera to compensate for the lighting conditions. Most people are well aware and used to using the RBG color space but it is a poor performer for what I wanted to do. I perfered to use the HSV color space see  but as I wanted to reduce image processing for real time speed I ended up using the raw data that comes from the camera sensor in YUV color space before it is processed into RGB then I would have to process it again into HSV. For details on YUV color space see  . The Y componet  of YUV is the brightness of a pixel so I just found the mean Y of the whole image and adjusted the brightness to get the mean that I was after.

Here's the code to find mean brightness of the video stream:

for frame in camera.capture_continuous(rawCapture, format="raw", use_video_port=True):
  image = frame.array
  (Y,U,V,DA)= cv2.mean(image) 

Method for detecting the cube

I would weed out most of unwanted data by just selecting the exact range of YUV that I wanted for the colors that I was looking for. I had glued Lego bricks to the center tiles so that the Lego motors can turn the faces and these Lego bricks were different shades and slightly different tints to the cube tiles so in reality I was looking for 12 colors not 6. In the end I found that I had to use 5 different range masks to capture all 12 colours but at the same time weed out most of the excess data in the image, then join all 5 masks together. All range masks are in binary (i.e each pixel only uses one bit, either on/off if it is in range) this makes for very fast processing compared to normal image that has 3 bytes for each pixel

Original image in raw YUV format from the camera.
Here's the code for the white, yellow range mask:
  White_Yellow_mask = cv2.inRange(image, (100,40,90), (255,255,255))
Output image from code.

Here's the code for the red, orange range mask:
  Red_mask= cv2.inRange(image, (0,0,143), (255,255,255))
Output image from code
 Here's the code for the green range mask:
  Green_mask = cv2.inRange(image, (60,50,50), (150,170,110))
Output image from code
I had to have a separate range mask for the center green Lego tile as it was very dark green and the tiles were a fluro green 
Here's the code for the center green range mask
  Center_Green_Mask = cv2.inRange(image, (20,60,50), (80,130,110))
The output image is empty because in this image we aren't looking at green face.
Here's the code for the blue range mask
  Blue_Mask = cv2.inRange(image, (20,95,50), (90,200,115))
Output image from code
Here's the code to join all 5 range masks together
  Combined_image = cv2.bitwise_or(White_Yellow_mask, Red_mask)
  Combined_image = cv2.bitwise_or(Green_mask, Combined_image)
  Combined_image = cv2.bitwise_or(Center_Green_Mask, Combined_image)
  Combined_image = cv2.bitwise_or(Blue_Mask, Combined_image)
Output image from code

I use the find contour function from OpenCV to find all the shapes in the image.
Here's the code
 im2,contours2, hierarchy = cv2.findContours(Combined_image.copy(),cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)
Here is what it finds
I use the OpenCV function that approximates lines, i.e if a line is a bit curvy it will take the curves out to a straight line for me.
Here's the code
  peri = cv2.arcLength(c, True)
  approx = cv2.approxPolyDP(c, 0.06 * peri, True)
I then look for countours with only 4 lines i.e squares, rectangles, diamonds, rhombus, trapezoids.
  if len (approx) ==4 :
I will get a bounding rectangle around the contour 
  (x, y, w, h) = cv2.boundingRect(approx)
I will calculate it's aspect ratio 
  ar = w / float(h)
I will get the area of the countour 
  area= cv2.contourArea(contours2[index])
If the aspect ratio is close to 1 i.e it is square in shape not rectangle or trapezoids and the size of it's width is in the range of what I am looking for and the area of the contour is close to the area of the bounding rectangle i.e not a diamond rhombus then it is probably the tile that I am looking for so add it to my list of possible candidates
Here's the code
  if ar > .7 and ar < 1.3 and w > 30 and w < 90 and area/(w*h) > .4:
This is what we are left with
In this particular image we aren't left with any false positives but sometimes something in the back ground could have been in right range so to be included in the range masks and if it is square in shape it will also be included at this stage. I remove then using the lonely neighbor rule. I loop through all the candidates and count up how many other candidates are within 3.5 * the width of the candidate and any candidates that has less than 5 neighbors then I will remove him from the list
Here's the code
  for d in new:
    (x,y,w,h) = d
    for (x2,y2,w2,h2) in new:
      if abs(x-x2) < (w*3.5) and abs(y-y2) < (h*3.5):
        neighbors +=1
    if neighbors < 5 :
 Then if there is 9 candidates left I sort then vertically then horizontally so that they are all in the right order for color detection. I won't post the code here but you can find it from the link about to the whole code.

Now the trickiest part of all, to identify the colors. It was very hard to find rules that would work in all lighting conditions but in the end I found what worked and again follow the link to the whole code to see this.

The detection process doesn't need the image to be converted to RGB but it is nice for an user interface to show it in RGB. So I covert it to RGB
Here's the code
  image = cv2.cvtColor(image, cv2.COLOR_YUV2RGB)
Now draw circles  on the image where all the candidates are at
  for (x,y,w,h) in candidates:, (x+w/2, y+h/2), int(w/1.8), (255,0,255),3)
Here what the output image looks like now
Based upon what the color of the center tile is which side it is. Once it has found all 6 sides and has checked that it has a total of 9 of each color between all 6 side then it will write the results to a file for the Small Basic program to access and solve the cube based upon.




No comments:

Post a Comment