Given an input image, it was an interesting problem to convert it into a gradient image, to extract objects in it and to approximate those objects to line segments.
First of all a binary threshold was applied to the image, with the threshold value taken from user. This process simplifies the image by reducing its colors to just two.
Next, the resulting binary image was dilated using the following structuring element.
010
111
010
The resulting image was a dilated form of the original image.
When original image was subtracted from this dilated image, we got crisp one pixel wide boundaries objects in the image.
For extracting objects as chains of pixels, a two-dimensional table was maintained, which contained all objects as pixels belonging to them in sequence.
1. Scan image until a point is found
2. If this point has not been visited yet
Mark it as visited
Store it in data structure
Check the points neighborhood for 8-connectivity
3 If a point is found Repeat step 2 for the new point
4 Else return
Polygonal Approximation
Output of the object extraction function was used as input to the polygonal
approximation function
Algorithm:
For each object
1. Assume first and last points form a line segment
2. Check perpendicular distance of all points lying between these two points
from the line joining these two points
3. Find the point with maximum distance
4. If maximum distance is less than a threshold, the two points form a line
segment
5. Else repeat the procedure with
First point and most distant point as last point
Most distant point as first point and last point
This one is a recursive function!
The rest is clear through the code. Have a nice day.
#include <X11/Intrinsic.h>
#include <X11/StringDefs.h>
#include <X11/Xaw/Command.h>
#include <X11/Xaw/Box.h>
#include <X11/Xresource.h>
#include <X11/Xaw/List.h>
#include <X11/Xaw/Dialog.h>
#include <X11/Xutil.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
/* Private files */
#include "./Scale.h"
/** Definitions : Dimensions & Types **/
#define NBIM 5 /* Nbre d'images */
#define ImageHeight 512
#define ImageWidth 512
#define WCOORDWIDTH 60
#define WCOORDHEIGHT 70
#define WPALETWIDTH 512
#define WPALETHEIGHT 25
#define WSLIDERWIDTH WPALETWIDTH + 150
#define WSLIDERHEIGHT 150
#define WCOMWIDTH 50
#define WCOMHEIGHT 800
#define WCOMMANDWIDTH 100
#define WCOMMANDHEIGHT 450
#define FrameHeight WCOORDHEIGHT+WCOMMANDHEIGHT+150 /* form widgets perform
clipping */
#define FrameWidth WCOMWIDTH + 2 * ImageWidth +100 /* so adjust the size to see
everything */
#define ScaleWidth 150
#define ScaleHeight 40
#define BorderColor 100
#define BorderWidth 1
/***** Couleurs ******/
#define RED 250
#define GRAY 251
#define BLUE 252
#define GREEN 253
#define WHITE 254
#define BLACK 255
/******* Type definition ********/
typedef unsigned char Image[ImageHeight][ImageWidth];
struct point
{
unsigned int x,y;
float distance;
} chains[1000][1000]; /*Chains of love*/
struct line
{
unsigned char x1,y1,x2,y2;
} lines[1000][1000]; /*Line segments all around*/
/******* Reservations : Images *****/
extern Image im[NBIM];
extern int scalebin;
/******* Other Declarations ********/
unsigned char followed[ImageHeight][ImageWidth]; /*Keeps track of followed
links*/
unsigned int objIndex; /*Number of objects*/
void Prog1() /*Preprocessing*/
{
int i,j;
int val=GetScaleValue(scalebin);
/************** CLEANUP ************************/
objIndex=0;
for(i=0;i<ImageHeight;i++)
for(j=0;j<ImageWidth;j++)
{
im[1][i][j]=0;
im[2][i][j]=0;
followed[i][j]=0;
}
/************** THRESHOLDING *******************/
for(i=0;i<ImageHeight;i++)
for(j=0;j<ImageWidth;j++)
{
if(im[0][i][j]<=val)
im[1][i][j]=0;
else
im[1][i][j]=255;
}
/*************** DIALATION *********************/
for(i=0;i<ImageHeight;i++)
for(j=0;j<ImageWidth;j++)
{
if( im[1][i][j]==255||
im[1][i+1][j]==255||
im[1][i-1][j]==255||
im[1][i][j-1]==255||
im[1][i][j+1]==255)
{
im[2][i][j]=255;
}
}
/*************** Subtract It ! ****************/
for(i=0;i<ImageHeight;i++)
for(j=0;j<ImageWidth;j++)
{
im[2][i][j]=im[2][i][j]-im[1][i][j];
}
DisplayRight(im[2]);
}
void Prog2() /*Object extraction and writing to file*/
{
int i,j,k;
for(i=0;i<ImageHeight;i++)
for(j=0;j<ImageWidth;j++)
{
if(followed[i][j]==0 && im[2][i][j]==255)
follow(i,j);
}
drawchains();
for(i=0;i<objIndex;i++)
{
lineseg(i,1,(int)chains[i][0].x); /*Approximate lines for each chain*/
}
}
void Prog3()
{
}
/**************** Follow me to paradise *************/
follow(int newx,int newy) /*Starting points*/
{
int i,j; /*Utility variables*/
unsigned int flag=1,found=0,pointIndex=1; /*Point Index is the number of points
per object*/
followed[newx][newy]=255;
while(flag==1)
{
for(i=-1;i<=1;i++)
for(j=-1;j<=1;j++)
{
if( im[2][newx+i][newy+j]==255 /*There is a way*/
&& followed[newx+i][newy+j]==0 /*And that way has not been followed*/
&& newx+i>=0 && newx+i<ImageWidth /*And I am not slipping off the edge*/
&& newy+j>=0 && newy+j<ImageHeight)
{
found=1;
newx=newx+i; /*Move to next point*/
newy=newy+j;
followed[newx][newy]=255;
chains[objIndex][pointIndex].x=newx; /*Link to chain*/
chains[objIndex][pointIndex].y=newy;
pointIndex++;
}
}
if(found==0) flag=0; /*Dead end!!!*/
else found=0; /*I am set to move to next point*/
}
chains[objIndex][0].x=pointIndex-1; /*Storing number of points per object.
Clever!!!*/
if(pointIndex>=5)objIndex++;
}
/*********** Line segments all over the land **********/
lineseg(int index,int begin,int end)
{
unsigned int i,j,k,max;
float m,c,x1,x2,y1,y2;
if(end-begin<1) return;
/*Evaluate useful variables*/
x1=(float)chains[index][begin].x; y1=(float)chains[index][begin].y;
x2=(float)chains[index][end].x; y2=(float)chains[index][end].y;
m=(y2-y1)/(x2-x1); c=y1-m*x1;
for(i=begin+1;i<end;i++) /*Find distances*/
{
if(y1==y2) chains[index][i].distance=abs((float)chains[index][i].y-y1);
else if(x1==x2) chains[index][i].distance=abs((float)chains[index][i].x-x1);
else
chains[index][i].distance=
fabs((m*(float)chains[index][i].x-(float)chains[index][i].y+c))/pow((pow(m,2)),0.5);
}
max=begin+1; /*Find the index of maximum*/
for(i=begin+2;i<end;i++)
{
if(chains[index][i].distance>chains[index][max].distance) max=i;
}
k=GetScaleValue(scalebin);
if(chains[index][max].distance<k) /*If the difference is too small*/
{
VectorLeft(chains[index][begin].y,chains[index][begin].x,
chains[index][end].y,chains[index][end].x,250);
return;
}
else /*Or else ...*/
{
if(max!=end) lineseg(index,begin,max);
if(max!=begin) lineseg(index,max,end);
}
}
drawchains() /*Draw chains of pixels from data structure*/
{
int i,j,k;
for(i=0;i<ImageHeight;i++)
for(j=0;j<ImageWidth;j++)
{
im[4][i][j]=0;
}
for(i=0;i<objIndex;i++)
{
for(j=1;j<chains[i][0].x;j++)
{
im[4][(int)chains[i][j].x][(int)chains[i][j].y]=255;
}
}
DisplayLeft(im[4]);
}
*****