Ve bir labirent bir görüntü verilen temsil çözmek için en iyi yolu nedir?

JPEG görüntü yukarıda görüldüğü gibi) göz önüne alındığında, okuma, bazı veri yapısı içine ayrıştırmak ve labirent çözmek için en iyi yolu nedir? Benim ilk içgüdüsü okuma görüntüde piksel piksel ve mağaza içinde bir liste (dizi) boolean değerleri: True bir beyaz piksel ve False olmayan bir beyaz piksel (renkler olabilir. sokak). Bu yöntem ile sorunu, görüntü olmayabilir "mükemmel". piksel Bu sadece beyaz bir piksel bir yerde bir duvarda ise orada istenmeyen bir yol yaratabilir.

Başka bir yöntem düşündüm biraz sonra bana geldi) yolları bir tuval üzerine çizilen bir listesi SVG dosyası - resmi dönüştürmek. Bu şekilde, yolları True bir yolu veya duvarı, False Seyahat mümkün bir alanı gösteren gösterir liste aynı tür içine okuma (boolean değer) olabilir. Bu yöntem ile ilgili bir sorun varsa dönüşüm 0 doğru değildir, ve tam olarak tüm duvarlar, boşluklar oluşturma bağlantı değilse ortaya çıkar.

Ayrıca SVG dönüştürme ile ilgili bir sorun çizgileri "mükemmel" düz olmayan. Bu kübik bezier eğrileri olmanın yollarını açar. Bir liste (dizi) boolean değerleri endeksli tarafından tamsayılar, eğriler olmaz transfer kolay, ve tüm noktaları bu hat üzerinde eğri olur olmak zorunda hesaplanan, ama olmayacak tam olarak eşleşmesi listesi endeksleri.

Bu yöntemlerden biri olsa da ne yazık ki bu kadar büyük bir imaj verimsiz oldukları iş muhtemelen olmasa da, daha iyi bir yolu var olduğunu varsayıyorum. Bu nasıl en iyi (en verimli ve/veya en az karmaşıklığı ile) yapılır? Hatta iyi bir yolu var mı?

Sonra gelen labirent çözme. Eğer ilk iki yöntemden birini kullanırsam, aslında bir matris ile sona erecek. this answer, bir labirent göstermek için iyi bir yol göre bir ağaç, ve A* algorithm kullanıyor çözmek için iyi bir yol kullanarak. Nasıl bir görüntü bir ağaç oluşturmak istiyorsunuz? Herhangi bir fikir?

TL;DR
Ayrıştırmak için en iyi yolu? Ne veri yapısı? Nasıl dedi yapı/çözme engel yardımcı olur mu?

GÜNCELLEME
Ne @Mikhail Python, @numpy kullanarak yazmıştır hayata elimi denedim Thomas önerilir. Algoritma doğru olduğunu hissediyorum, ama umduğu gibi gitmiyor. (Aşağıda kodu.) PNG kitaplığı PyPNG.

import png, numpy, Queue, operator, itertools

def is_white(coord, image):
  """ Returns whether (x, y) is approx. a white pixel."""
  a = True
  for i in xrange(3):
    if not a: break
    a = image[coord[1]][coord[0] * 3   i] > 240
  return a

def bfs(s, e, i, visited):
  """ Perform a breadth-first search. """
  frontier = Queue.Queue()
  while s != e:
    for d in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
      np = tuple(map(operator.add, s, d))
      if is_white(np, i) and np not in visited:
        frontier.put(np)
    visited.append(s)
    s = frontier.get()
  return visited

def main():
  r = png.Reader(filename = "thescope-134.png")
  rows, cols, pixels, meta = r.asDirect()
  assert meta['planes'] == 3 # ensure the file is RGB
  image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels))
  start, end = (402, 985), (398, 27)
  print bfs(start, end, image2d, [])

İşte bir çözüm.

1. Görüntü son görüntü gri üniformalı yaklaşık bu kadar (henüz ikili), renk ayarlama ağırlıkları gri tonlama dönüştürmek. Sadece - ^ Görüntü Photoshop sürgü kontrol ederek yapabilirsin . Ayarlar ->Siyah & Beyaz.
2. Resim - ^ Görüntü Photoshop'ta uygun eşik ayarlayarak ikiliye dönüştürür . Ayarlar ->Eşik.
3. Eşik doğru seçili olduğundan emin olun. 0 tolerans, nokta örneği ile Sihirli Değnek Aracı, bitişik, anti-aliasing yok. Hangi seçim tatili yanlış kenarları yanlış eşik tarafından sunulan olmayan kenarları kontrol edin. Aslında, bu labirent tüm iç noktaları baştan erişilebilir.
4. Labirent yapay sınırları sanal gezgin dolaşmak:) olmaz emin olmak için ekleyin
5. En sevdiğiniz dil breadth-first search (BFS) uygulamak ve baştan çalıştırın. Bu görev için MATLAB tercih ederim. @Thomas daha önce de belirtildiği gibi, grafikler düzenli temsil karıştırmaya gerek yok. Binarized görüntü ile doğrudan çalışabilirsiniz.

Burada BFS için MATLAB kodu:

function path = solve_maze(img_file)
  %% Init data
  img = imread(img_file);
  img = rgb2gray(img);
  maze = img > 0;
  start = [985 398];
  finish = [26 399];

  %% Init BFS
  n = numel(maze);
  Q = zeros(n, 2);
  M = zeros([size(maze) 2]);
  front = 0;
  back = 1;

  function push(p, d)
    q = p   d;
    if maze(q(1), q(2)) && M(q(1), q(2), 1) == 0
      front = front   1;
      Q(front, :) = q;
      M(q(1), q(2), :) = reshape(p, [1 1 2]);
    end
  end

  push(start, [0 0]);

  d = [0 1; 0 -1; 1 0; -1 0];

  %% Run BFS
  while back <= front
    p = Q(back, :);
    back = back   1;
    for i = 1:4
      push(p, d(i, :));
    end
  end

  %% Extracting path
  path = finish;
  while true
    q = path(end, :);
    p = reshape(M(q(1), q(2), :), 1, 2);
    path(end   1, :) = p;
    if isequal(p, start) 
      break;
    end
  end
end

Python Bu uygulama konusunda sıkıntı olmamalı ya da her neyse gerçekten çok basit ve standart.

Ve işte cevabı: