Implementation of feature detection algorithm

Question

I'm fairly new to programming and would like to know how to start implementing the following algorithm in C++,

Given a binary image where pixels with intensity 255 show edges and pixels with intensity 0 show the background, find line segments longer than n pixels in the image. t is a counter showing the number of iterations without finding a line, and tm is the maximum number of iterations allowed before exiting the program.

1. Let t=0.
2. Take two edge points randomly from the image and find equation of the line passing through them.
3. Find m, the number of other edge points in the image that are within distance d pixels of the line.

4. If m > n, go to Step 5.

   Otherwise (m ≤ n), increment t by 1 and if t < tm go to Step 2, and if t ≥ tm exit program.

5. Draw the line and remove the edge points falling within distance d pixels of it from the image. Then, go to Step 1

Basically, I just want to randomly pick two points from the image, find the distance between them, and if that distance is too small, I would detect a line between them.

I would appreciate if a small code snippet is provided, to get me started. this is more like a RANSAC parametric line detection. I would also keep this post updated if I get it done.

/* Display Routine */

#include "define.h"

ByteImage bimg;                     //A copy of the image to be viewed
int width, height;                  //Window dimensions
GLfloat zoomx = 1.0, zoomy = 1.0;   //Pixel zoom
int win;                            //Window index

void resetViewer();

void reshape(int w, int h) {
glViewport(0, 0, (GLsizei)w, (GLsizei)h);
if ((w!=width) || (h!=height)) {
    zoomx=(GLfloat)w/(GLfloat)bimg.nc;
    zoomy=(GLfloat)h/(GLfloat)bimg.nr;
    glPixelZoom(zoomx,zoomy);
}
width=w; height=h;

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0.0, (GLdouble)w, 0.0, (GLdouble)h);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
}

void mouse(int button, int state, int x, int y) {
glutPostRedisplay();
if((button == GLUT_LEFT_BUTTON) && (state == GLUT_DOWN) &&
    (zoomx==1.0) && (zoomy==1.0)){
printf(" row=%d, col=%d, int=%d.\n", y,x, (int)bimg.image[(bimg.nr-1-y)*bimg.nc+x]);
        glutPostRedisplay();
}
}

void display() {
glClear(GL_COLOR_BUFFER_BIT);
glRasterPos2i(0, 0);         
glPixelStorei(GL_UNPACK_ALIGNMENT, 1);

glDrawPixels((GLsizei)bimg.nc,(GLsizei)bimg.nr,   GL_LUMINANCE,GL_UNSIGNED_BYTE, bimg.image);
glutSwapBuffers();
}

Answer 1

Let us assume you have an int[XDIMENSION][YDIMENSION]

Let t=0.

int t = 0; // ;-)

Take two edge points randomly from the image and find equation of the line passing through them.

Brute force: you could randomly search the image for points and re-search when they are not edge points

struct Point {
  int x;
  int y;
};

bool is_edge(Point a) {
  return image[a.x][a.y] == 255;
}

int randomUpto(int upto) {
  int r = rand() % upto;
  return r;
}

, which needs the pseudo-random number generator to be initialized via

srand(time(NULL));

To find edge points

  Point a;
  do {
    a.x = randomUpto(XDIMENSION);
    a.y = randomUpto(YDIMENSION);
  } while ( ! is_edge(a) );

Find m, the number of other edge points in the image that are within distance d pixels of the line.

You need the line between the points. Some searching yields this fine answer, which leads to

std::vector<Point> getLineBetween(Point a, Point b) {
  double dx = b.x - a.x;
  double dy = b.y - a.y;
  double dist = sqrt(dx * dx + dy * dy);
  dx /= dist;
  dy /= dist;
  std::vector<Point> points;
  points.push_back(a);
  for ( int i = 0 ; i < 2*dist; i++ ) {
    Point tmp;
    tmp.x = a.x + (int)(i * dx /2.0);
    tmp.y = a.y + (int)(i * dy /2.0);
    if ( tmp.x != points.back().x
     || tmp.y != points.back().y ) {
      points.push_back(tmp);
    }
  }
  return points;
}

Do you see a pattern here? Isolate the steps into substeps, ask google, look at the documentation, try out stuff until it works.

Your next steps might be to

• create a distance function, euclidean should suffice
• find all points next to line (or next to a point, which is easier) based on the distance function

Try out some and come back if you still need help.