Solucionando um labirinto usando transformação morfológica

Neste post vou mostrar como resolver um labirinto usando transformação morfológica, e como bônus você pode aprender o básico de processamento de imagens usando o EmguCV .

O código funciona para "labirintos perfeitos", são labirintos que tem somente um caminho de um ponto ao outro, sem seções, sem caminhos circulares e sem áreas abertas.

Para gerar os labirintos eu usei essa ferramenta online maze generator. Imagem para os testes:

Abrindo a imagem:

Image<Bgr, Byte> src = new Image<Bgr, byte>("ImageGenerator.png");

Convertendo a imagem para binário

Image<Gray, Byte> bw = src.Convert<Gray, Byte>(); bw = bw.ThresholdBinaryInv(new Gray(10), new Gray(255));

Note que estamos usando um threashold invertido para obter a imagem binária. Isso nos dará uma imagem onde as paredes serão brancas ao invés de pretas.

Encontrando as paredes obtendo os contornos,

VectorOfVectorOfPoint contours = new VectorOfVectorOfPoint(); IOutputArray hirarchy; CvInvoke.FindContours(bw.Mat, contours, new Mat(), Emgu.CV.CvEnum.RetrType.External, Emgu.CV.CvEnum.ChainApproxMethod.ChainApproxNone); if (contours.Size != 2) { // "Labirinto perfeito" precisa ter duas paredes Console.WriteLine("Este não é um labirinto perfeito"); return; }

Estamos assumindo que este é um labirinto perfeito que tem somente duas paredes. Pegamos a primeira parede,

Image<Gray, Byte> path = new Image<Gray, byte>(src.Size); CvInvoke.DrawContours(path,contours,0,new MCvScalar(255,255,255),0,LineType.FourConnected);

Para aqueles que conhecem pouco de morfologia segue um ótimo texto: Morfologia Matemática para imagens em tons de cinza.

Dilatamos a parede em alguns pixels.

//Tente usar diferentes valores path = path.Dilate(10);

Erode a mesma quantidade de pixes

Image<Gray, Byte> path_erode = path.Erode(10);

Agora temos a imagem "dilatada" e "erodida" conseguimos a solução subtraindo uma da outra.

path = path_erode.AbsDiff(path);

Desenharemos a solução em vermelho na imagem de resultado.

var channels = src.Split(); channels[0] &= ~path; channels[1] &= ~path; channels[2] |= path;

VectorOfMat c = new VectorOfMat(); c.Push(channels[0]); c.Push(channels[1]); c.Push(channels[2]);

Image<Bgr, Byte> dst = new Image<Bgr, byte>(src.Size); CvInvoke.Merge(c,dst);