python एक छवि दिया एक भूलभुलैया का प्रतिनिधित्व और हल




algorithm matlab (7)

वृक्ष खोज बहुत अधिक है। भूलभुलैया समाधान पथ (पथों) के साथ निहित रूप से अलग है।

(Reddit से rainman002 के लिए धन्यवाद यह मुझे इंगित करने के लिए।)

इस वजह से, आप भूलभुलैया दीवारों के जुड़े वर्गों की पहचान करने के लिए त्वरित रूप से जुड़े घटकों का उपयोग कर सकते हैं। यह दो बार पिक्सल पर फिर से चलाता है।

यदि आप इसे समाधान पथ के अच्छे आरेख में बदलना चाहते हैं, तो आप प्रत्येक कनेक्टेड क्षेत्र के लिए "मृत अंत" मार्गों को भरने के लिए संरचना तत्वों के साथ बाइनरी संचालन का उपयोग कर सकते हैं।

MATLAB के लिए डेमो कोड निम्नानुसार है। यह परिणाम को बेहतर तरीके से साफ करने के लिए tweaking का उपयोग कर सकता है, इसे और अधिक सामान्य बनाने के लिए, और इसे तेजी से चलाने के लिए। (कभी-कभी जब यह 2:30 बजे नहीं होता है।)

% read in and invert the image
im = 255 - imread('maze.jpg');

% sharpen it to address small fuzzy channels
% threshold to binary 15%
% run connected components
result = bwlabel(im2bw(imfilter(im,fspecial('unsharp')),0.15));

% purge small components (e.g. letters)
for i = 1:max(reshape(result,1,1002*800))
    [count,~] = size(find(result==i));
    if count < 500
        result(result==i) = 0;
    end
end

% close dead-end channels
closed = zeros(1002,800);
for i = 1:max(reshape(result,1,1002*800))
    k = zeros(1002,800);
    k(result==i) = 1; k = imclose(k,strel('square',8));
    closed(k==1) = i;
end

% do output
out = 255 - im;
for x = 1:1002
    for y = 1:800
        if closed(x,y) == 0
            out(x,y,:) = 0;
        end
    end
end
imshow(out);

छवि को देखते हुए भूलभुलैया का प्रतिनिधित्व करने और हल करने का सबसे अच्छा तरीका क्या है?

एक जेपीईजी छवि (जैसा कि ऊपर देखा गया है) को देखते हुए, इसे पढ़ने के लिए सबसे अच्छा तरीका क्या है, इसे कुछ डेटा संरचना में पार्स करें और भूलभुलैया को हल करें? मेरी पहली प्रवृत्ति पिक्सेल में पिक्सेल द्वारा छवि को पढ़ने और इसे बूलियन मानों की एक सूची (सरणी) में संग्रहीत करना है: एक सफेद पिक्सेल के लिए True , और एक गैर-सफेद पिक्सेल के लिए False (रंगों को त्याग दिया जा सकता है)। इस विधि के साथ समस्या यह है कि छवि "पिक्सेल सही" नहीं हो सकती है। इसके द्वारा मेरा मतलब यह है कि अगर दीवार पर कहीं एक सफेद पिक्सेल है तो यह एक अनजान पथ बना सकता है।

एक और तरीका (जो थोड़ा सा विचार के बाद मेरे पास आया) छवि को एक एसवीजी फ़ाइल में परिवर्तित करना है - जो कैनवास पर खींचे गए पथों की एक सूची है। इस तरह, पथों को उसी प्रकार की सूची (बूलियन मान) में पढ़ा जा सकता है जहां True पथ या दीवार को इंगित करता है, False एक यात्रा-सक्षम स्थान का संकेत देती है। इस विधि के साथ एक मुद्दा उत्पन्न होता है यदि रूपांतरण 100% सटीक नहीं है, और अंतराल को पूरी तरह से कनेक्ट नहीं करता है, अंतराल बना देता है।

एसवीजी में कनवर्ट करने के साथ ही एक मुद्दा यह है कि रेखाएं "पूरी तरह से" सीधे नहीं हैं। इसके परिणामस्वरूप घन बेजियर वक्र होते हैं। पूर्णांक द्वारा अनुक्रमित बूलियन मानों की एक सूची (सरणी) के साथ, वक्र आसानी से स्थानांतरित नहीं होंगे, और वक्र पर मौजूद सभी बिंदुओं की गणना की जानी चाहिए, लेकिन सूची सूचकांक से बिल्कुल मेल नहीं खाएंगे।

मुझे लगता है कि इन विधियों में से एक काम कर सकता है (हालांकि शायद नहीं) कि वे इतनी बड़ी छवि को दुखी अक्षम हैं, और यह कि एक बेहतर तरीका मौजूद है। यह सबसे अच्छा (सबसे कुशलतापूर्वक और / या कम से कम जटिलता के साथ) कैसे किया जाता है? क्या कोई सबसे अच्छा तरीका भी है?

फिर भूलभुलैया का हल आता है। अगर मैं पहले दो तरीकों में से किसी एक का उपयोग करता हूं, तो मैं अनिवार्य रूप से एक मैट्रिक्स के साथ समाप्त हो जाऊंगा। इस उत्तर के मुताबिक, भूलभुलैया का प्रतिनिधित्व करने का एक अच्छा तरीका एक पेड़ का उपयोग कर रहा है, और इसे हल करने का एक अच्छा तरीका ए * एल्गोरिदम का उपयोग कर रहा है । छवि से पेड़ कैसे बनायेगा? कोई विचार?

टी एल; डॉ
पार्स करने का सबसे अच्छा तरीका? किस डेटा संरचना में? संरचना कैसे मदद / बाधा हल करने में कहा जाएगा?

अद्यतन करें
मैंने numpy ने पायथन में लिखा है कि कार्यान्वित करने पर मेरे हाथों की कोशिश की है, जैसे कि @ थॉमस की सिफारिश की गई है। मुझे लगता है कि एल्गोरिदम सही है, लेकिन यह उम्मीद के रूप में काम नहीं कर रहा है। (नीचे कोड।) पीएनजी लाइब्रेरी 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, [])

यहां आप जाते हैं: maze-solver-python (गिटहब)

मुझे इसके साथ खेलना मजेदार था और यूसुफ केर्न के जवाब पर विस्तार हुआ। इससे अलग नहीं होना; मैंने अभी किसी और के लिए कुछ मामूली जोड़ किए हैं जो इस के साथ खेलने में रुचि रखते हैं।

यह एक पायथन आधारित सॉल्वर है जो सबसे कम पथ खोजने के लिए बीएफएस का उपयोग करता है। उस समय मेरे मुख्य परिवर्धन हैं:

  1. छवि खोज से पहले साफ हो जाती है (यानी शुद्ध काले और सफेद में परिवर्तित)
  2. स्वचालित रूप से एक जीआईएफ उत्पन्न करें।
  3. स्वचालित रूप से एक एवीआई उत्पन्न करें।

जैसा कि यह खड़ा है, इस नमूना भूलभुलैया के लिए स्टार्ट / एंड-पॉइंट हार्ड-कोड किए गए हैं, लेकिन मैं इसे विस्तारित करने की योजना बना रहा हूं कि आप उचित पिक्सल चुन सकें।


यह समाधान पायथन में लिखा गया है। छवि तैयारी पर पॉइंटर्स के लिए मिखाइल धन्यवाद।

एक एनिमेटेड ब्रेडथ-फर्स्ट सर्च:

पूर्ण भूलभुलैया:

#!/usr/bin/env python

import sys

from Queue import Queue
from PIL import Image

start = (400,984)
end = (398,25)

def iswhite(value):
    if value == (255,255,255):
        return True

def getadjacent(n):
    x,y = n
    return [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]

def BFS(start, end, pixels):

    queue = Queue()
    queue.put([start]) # Wrapping the start tuple in a list

    while not queue.empty():

        path = queue.get() 
        pixel = path[-1]

        if pixel == end:
            return path

        for adjacent in getadjacent(pixel):
            x,y = adjacent
            if iswhite(pixels[x,y]):
                pixels[x,y] = (127,127,127) # see note
                new_path = list(path)
                new_path.append(adjacent)
                queue.put(new_path)

    print "Queue has been exhausted. No answer was found."


if __name__ == '__main__':

    # invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.]
    base_img = Image.open(sys.argv[1])
    base_pixels = base_img.load()

    path = BFS(start, end, base_pixels)

    path_img = Image.open(sys.argv[1])
    path_pixels = path_img.load()

    for position in path:
        x,y = position
        path_pixels[x,y] = (255,0,0) # red

    path_img.save(sys.argv[2])

नोट: एक सफेद विज़िट पिक्सेल ग्रे चिह्नित करता है। यह किसी विज़िट की गई सूची की आवश्यकता को हटा देता है, लेकिन पथ को खींचने से पहले डिस्क से छवि फ़ाइल का दूसरा लोड आवश्यक होता है (यदि आप अंतिम पथ की समग्र छवि और सभी पथों को नहीं लेना चाहते हैं)।

मैंने इस्तेमाल किए गए भूलभुलैया का एक खाली संस्करण।


मैं मैट्रिक्स-ऑफ-बूल विकल्प के लिए जाऊंगा। यदि आपको लगता है कि मानक पायथन सूची इसके लिए बहुत अक्षम हैं, तो आप इसके बजाय numpy.bool सरणी का उपयोग कर सकते हैं। 1000x1000 पिक्सेल भूलभुलैया के लिए संग्रहण केवल 1 एमबी है।

किसी पेड़ या ग्राफ डेटा संरचनाओं को बनाने से परेशान न हों। यह इसके बारे में सोचने का एक तरीका है, लेकिन स्मृति में इसका प्रतिनिधित्व करने के लिए जरूरी नहीं है; एक बूलियन मैट्रिक्स कोड और अधिक कुशल दोनों आसान है।

फिर इसे हल करने के लिए ए * एल्गोरिदम का उपयोग करें। दूरी हेरिस्टिक के लिए, मैनहट्टन दूरी ( distance_x + distance_y ) का उपयोग करें।

(row, column) निर्देशांक के एक tuple द्वारा नोड्स का प्रतिनिधित्व करें। जब भी एल्गोरिदम ( विकिपीडिया स्यूडोकोड ) "पड़ोसियों" के लिए कॉल करता है, तो यह चार संभावित पड़ोसियों (छवि के किनारों को ध्यान में रखकर) पर लूपिंग का एक साधारण मामला है।

यदि आपको लगता है कि यह अभी भी बहुत धीमा है, तो आप इसे लोड करने से पहले छवि को डाउनस्केल करने का प्रयास कर सकते हैं। प्रक्रिया में किसी भी संकीर्ण पथ को खोने से सावधान रहें।

शायद पाइथन में 1: 2 डाउनस्कलिंग करना संभव है, यह जांच कर कि आप वास्तव में किसी भी संभावित पथ को खो नहीं सकते हैं। एक दिलचस्प विकल्प है, लेकिन इसे थोड़ा और विचार चाहिए।


एक थ्रेसहोल्ड निरंतर भरने के लिए एक कतार का उपयोग करता है। प्रवेश द्वार के पिक्सेल को कतार पर छोड़ देता है और फिर लूप शुरू करता है। यदि एक कतारबद्ध पिक्सेल पर्याप्त अंधेरा है, तो यह रंगीन हल्का भूरा (थ्रेसहोल्ड से ऊपर) है, और सभी पड़ोसियों को कतार पर धकेल दिया जाता है।

from PIL import Image
img = Image.open("/tmp/in.jpg")
(w,h) = img.size
scan = [(394,23)]
while(len(scan) > 0):
    (i,j) = scan.pop()
    (r,g,b) = img.getpixel((i,j))
    if(r*g*b < 9000000):
        img.putpixel((i,j),(210,210,210))
        for x in [i-1,i,i+1]:
            for y in [j-1,j,j+1]:
                scan.append((x,y))
img.save("/tmp/out.png")

समाधान ग्रे दीवार और रंगीन दीवार के बीच गलियारा है। ध्यान दें कि इस भूलभुलैया में कई समाधान हैं। इसके अलावा, यह केवल काम करने लगता है।


यहां एक समाधान है।

  1. छवि को ग्रेस्केल (अभी तक बाइनरी) में कनवर्ट करें, रंगों के लिए वजन समायोजित करें ताकि अंतिम ग्रेस्केल छवि लगभग समान हो। आप छवि में फ़ोटोशॉप में स्लाइडर को नियंत्रित करके बस इसे कर सकते हैं -> समायोजन -> काला और सफेद।
  2. छवि में फ़ोटोशॉप में उचित दहलीज सेट करके छवि को बाइनरी में कनवर्ट करें -> समायोजन -> थ्रेसहोल्ड।
  3. सुनिश्चित करें कि थ्रेसहोल्ड सही चुना गया है। 0 सहिष्णुता, बिंदु नमूना, संगत, कोई एंटी-एलियासिंग के साथ जादू वंड टूल का उपयोग करें। उन किनारों को जांचें जिन पर चयन ब्रेक गलत थ्रेसहोल्ड द्वारा पेश किए गए झूठे किनारे नहीं हैं। वास्तव में, इस भूलभुलैया के सभी आंतरिक बिंदु शुरुआत से ही सुलभ हैं।
  4. यह सुनिश्चित करने के लिए कि आभासी यात्री इसके चारों ओर नहीं चलेगा भूलभुलैया पर कृत्रिम सीमाएं जोड़ें :)
  5. अपनी पसंदीदा भाषा में चौड़ाई-पहली खोज (बीएफएस) लागू करें और इसे शुरुआत से चलाएं। मैं इस काम के लिए MATLAB पसंद करते हैं। जैसा कि @ थॉमस पहले से ही उल्लेख किया गया है, ग्राफ के नियमित प्रतिनिधित्व के साथ गड़बड़ करने की कोई आवश्यकता नहीं है। आप सीधे बिनराइज्ड छवि के साथ काम कर सकते हैं।

बीएफएस के लिए MATLAB कोड यहां दिया गया है:

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 या जो भी हो, इसे लागू करने में कठिनाइयों नहीं होनी चाहिए।

और यहां जवाब है:


यहां कुछ विचार दिए गए हैं।

(1. छवि प्रसंस्करण :)

1.1 छवि को RGB पिक्सेल मानचित्र के रूप में लोड करें। C# system.drawing.bitmap का उपयोग करके यह छोटा है। इमेजिंग के लिए कोई आसान समर्थन नहीं वाली भाषाओं में, बस छवि को पोर्टेबल पिक्समैप प्रारूप (पीपीएम) (एक यूनिक्स टेक्स्ट प्रस्तुति, बड़ी फाइलें उत्पन्न करती है) या कुछ सरल बाइनरी फ़ाइल प्रारूप में परिवर्तित करें जिसे आप आसानी से पढ़ सकते हैं, जैसे BMP या TGA । विंडोज़ में यूनिक्स या IrfanView ImageMagick में ImageMagick

1.2 जैसा कि पहले बताया गया है, आप प्रत्येक पिक्सेल के लिए ग्रे टोन के संकेतक के रूप में (आर + जी + बी) / 3 ले कर डेटा को सरल बना सकते हैं और फिर काले और सफेद तालिका का उत्पादन करने के लिए मान को थ्रेसहोल्ड कर सकते हैं। 200 के करीब कुछ मानते हैं 0 = काला और 255 = सफेद जेपीईजी कलाकृतियों को बाहर ले जाएगा।

(2. समाधान :)

2.1 गहराई-पहली खोज: प्रारंभिक स्थान के साथ एक खाली ढेर में प्रवेश करें, उपलब्ध फॉलो-अप चालें एकत्र करें, यादृच्छिक रूप से एक चुनें और स्टैक पर दबाएं, अंत तक पहुंचने तक या एक मृतक तक आगे बढ़ें। स्टैक पॉप अप करके डेडेंड बैकट्रैक पर, आपको ट्रैक रखने की आवश्यकता है कि मानचित्र पर कौन सी स्थितियों का दौरा किया गया था ताकि जब आप उपलब्ध चालें एकत्र करते हैं तो आप कभी भी दो बार एक ही रास्ता नहीं लेते। एनिमेट करने के लिए बहुत दिलचस्प है।

2.2 ब्रेड-फर्स्ट सर्च: उपरोक्त के समान, पहले कतारों का उपयोग करके पहले उल्लेख किया गया। एनिमेट करने के लिए भी दिलचस्प है। यह छवि संपादन सॉफ्टवेयर में बाढ़ भरने की तरह काम करता है। मुझे लगता है कि आप इस चाल का उपयोग कर फ़ोटोशॉप में एक भूलभुलैया हल करने में सक्षम हो सकते हैं।

2.3 दीवार अनुयायी: ज्यामितीय रूप से बोलते हुए, एक भूलभुलैया एक गुना / घुलनशील ट्यूब है। यदि आप दीवार पर अपना हाथ रखते हैं तो आपको अंततः बाहर निकलना होगा;) यह हमेशा काम नहीं करता है। कुछ धारणाएं हैं: परिपूर्ण मैज इत्यादि, उदाहरण के लिए, कुछ मैज द्वीपों में होते हैं। इसे देखो; यह आकर्षक है।

(3. टिप्पणियाँ :)

यह मुश्किल है। मैज को सुलझाना आसान है यदि कुछ साधारण सरणी में औपचारिक रूप से प्रतिनिधित्व किया जाता है, प्रत्येक तत्व उत्तर, पूर्व, दक्षिण और पश्चिम दीवारों और एक दौरा ध्वज क्षेत्र वाला सेल प्रकार होता है। हालांकि यह देखते हुए कि आप इसे हाथ से तैयार किए गए स्केच दिए जाने की कोशिश कर रहे हैं, यह गन्दा हो जाता है। मैं ईमानदारी से सोचता हूं कि स्केच को तर्कसंगत बनाने की कोशिश करने से आपको पागल हो जाएगा। यह कंप्यूटर दृष्टि की समस्याओं के समान है जो काफी शामिल हैं। शायद छवि मानचित्र पर सीधे जाकर आसान और अधिक अपर्याप्त हो सकता है।





maze