2

I have a floor plan on which the walls are black, the doors are orange and the target is red. What I want is to make an app where given a specific point on the image, the route to the target is calculated and displayed. I already have a routing method, but it is in matlab and each position and object is defined in the code and it doesn't use an image. What I would like to know is how to scan the image to identify the walls, the doors and the target by color in order to apply the routing method and then display the route over the image of the map (I guess I should use drawable for that).

user1944013
  • 17
  • 2

2 Answers2

3

This are some steps to implement a pathfinding algorithmm from an image.

  • Upload your image
  • Apply a color detection HSV(in the real life is most easy control the light changes with this format) algorithm to obtain the objects separately.
  • Make a new binary Matrix with 1 for your floor and 0 to the obstacles.
  • Apply to that binary Matrix an Occupancy grid algorithm(this reduce your matrix because in the pathfinding algorithm you need processing).
  • and now ur path finding algorithm. I recommend use the diijistrak or A star algorithm, in this two cases you need construct an adjacency matrix.

The graph theory will help you to understand better.Good Luck!!

You can work in processing IDE for rapid prototipyng and migrate all the processing IDE core to eclipse, you need implement the PApplet class in your eclipse project, and can compile your app to Android.

Mario Alzate
  • 372
  • 3
  • 8
1

I would use somekind of occupancy grid/map where each grid cell = one pixel (or possibly a small collection of pixels like 2x2 3x3, etc) And just do k-means clustering on the image. There are a few choices for k

k=2

you have walls is one group (the black lines)

everything else is considered opened space (this assumes doors can be opened).

You will need to know where the red point is located, but it doens't need to be visible in your map. It is just another open space in your map. that your program internally knows is the endpoint.

k=4

a group for everything black=walls(occupied), orange=doors(may or may not look like occupied cells depending on whether or not they can be opened),red=target(unoccupied), white=open space(unoccupied).

In both cases you can generate labels for your clusters and use those in your map. I'm not sure what exactly your path finding algorithm is, but typically the goal is to minimize some cost function, and as such you assign a extremely high cost to walls (so they will never be crossed), possibly assign a medium cost to doors (in case they can't be opened). Just some ideas, good luck

andrew
  • 2,451
  • 1
  • 15
  • 22
  • Thanks for the helpful answer! Should I use bitmap methods for image analysis, or something else? Also, what about displaying the calculated route on the display? – user1944013 Apr 01 '15 at 12:29
  • the image type doesn't matter much. In matlab you just do `im=imread(your_im_file)` where `your_im_file` can be any supported file types http://www.mathworks.com/help/matlab/ref/imread.html?refresh=true once it's read into matlab it doens't matter what the original format was. You are able to manipulate the image jsut as you would manipulate any matrix. For drawing your path, see this SO question http://stackoverflow.com/questions/3533843/how-to-draw-a-line-on-an-image-in-matlab – andrew Apr 01 '15 at 16:25
  • But I want to do it in java for an android application, not matlab. The method I have happens to be in matlab and I want to convert it in order to make it work there. – user1944013 Apr 01 '15 at 16:28
  • I'm sorry I only know how to do it in matlab. Maybe add the **java** tag to your question and someone with more knowledge on java might come and help you. But in most other languages Bitmap is an easy format to work with because there is no compression, so every single pixel is perfectly represented in the image. From the javadocs you can draw lines in .awt.graphics http://docs.oracle.com/javase/7/docs/api/java/awt/Graphics.html#drawLine(int,%20int,%20int,%20int) here is and example http://www.javadocexamples.com/java/awt/Graphics/drawLine%28int%20x1,int%20y1,int%20x2,int%20y2%29.html – andrew Apr 01 '15 at 16:35