Recognizing tetris pieces in C

Question

Hello!!

I have to make an application that recognizes inside an black and withe image a piece of tetris givem by the user. I read the image to analyze into an array.

How can I do something like this using C?

Thanks and best regards.

Answer 1

You might not want to implement that from scratch (unless required, of course) ... I'd recommend looking for a suitable library. I've heard that OpenCV is good, but never done any work with machine vision myself so I haven't tested it.

Answer 2

Search for connected components (i.e. using depth-first search; you might want to avoid recursion if efficiency is an issue; use your own stack instead). The largest connected component should be your tetris piece. You can then further analyze it (using the shape, the size or some kind of border description)

Answer 3

Assuming that you already loaded the images into arrays, what about using regular expressions? You don't need exact shape matching but approximately, so why not give it a try!

Edit: I downloaded your doc file. You must identify a random pattern among random figures on a 2D array so regex isn't suitable for this problem, lets say that's the bad news. The good news is that your homework is not exactly image processing, and it's much easier.

It's your homework so I won't create the code for you but I can give you directions.

1. You need a routine that can create a new piece from the original pattern/piece rotated. (note: with piece I mean the 4x4 square - all the cells of it)
2. You need a routine that checks if a piece matches an area from the 2D image at position x,y - the matching area would have corners (x-2, y-2, x+1, y+1).
3. You search by checking every image position (x,y) for a match.

Since you must use parallelism you can create 4 threads and assign to each thread a different rotation to search.

Answer 4

Looking at the shapes given for tetris pieces in Wikipedia, called "I,J,L,O,S,T,Z", it seems that the ratios of the sides of the bounding box (easy to find given a binary image and C) reveal whether you have I (4:1) or O (1:1); the other shapes are 2:3.

To detect which of the remaining shapes you have (J,L,S,T, or Z), it looks like you could collect the length and position of the shape's edges that fall on the bounding box's edges. Thus, T would show 3 and 1 along the 3-sides, and 1 and 1 along the 2 sides. Keeping track of the positions helps distinguish J from L, S from Z.