home *** CD-ROM | disk | FTP | other *** search
/ vis-ftp.cs.umass.edu / vis-ftp.cs.umass.edu.tar / vis-ftp.cs.umass.edu / pub / Software / ASCENDER / ascender.tar.Z / ascender.tar / BuildingFinder / polygons.h < prev    next >
C/C++ Source or Header  |  1996-03-05  |  11KB  |  413 lines
  1. /*
  2.  *    Polygons.h
  3.  *
  4.  *  Important definitions for the perceptual grouping routines
  5.  * used in the building detector.  
  6.  *
  7.  * Christopher Jaynes
  8.  * March, 10 1995
  9.  * ASCENDER System
  10.  *
  11.  * UMass RADIUS-VISIONS Group.
  12.  * 
  13.  *
  14.  */
  15.  
  16. #include <stdio.h>
  17. #include <math.h>
  18. #include "rcde_types.h"
  19.  
  20. #define    TRUE        1
  21. #define FALSE        0
  22.  
  23.  
  24. #define LINE_WIDTH    2
  25.  
  26. #define SQ(x)        ((x)*(x))
  27.  
  28. #define PI        3.141
  29.  
  30. #define MB1_SCALE    (500.0/12.0)
  31.  
  32.  
  33. char IMAGE_NAME[80];
  34. char IMAGE_NAME_3D[80];
  35.  
  36.  
  37. #define LOW                0
  38. #define MEDIUM                1
  39. #define HIGH                2
  40.  
  41. #define EMPTY        0
  42. #define USED        1
  43.  
  44. #define LINE        3
  45.  
  46. #define NONE        0
  47.  
  48. #define MAXCHAINLEN        8
  49. #define WINDOW            8
  50. #define MIN_LINE_LENGTH        5
  51. #define MAX_ALLOWED_COLOR 700           /* Was 550, max search depth in FRG */
  52.  
  53.  
  54.  
  55. #define    IMAGE_VAR        1.5    /* Expected error, in pixels */
  56.  
  57.  
  58. #define DEFAULT_ANGLE_THRESH_HIGH    0.25 /* 14.3 degrees */
  59. #define DEFAULT_LINE_SUPPORT_HIGH    0.5
  60. #define TOKEN_SUPPORT_HIGH        0.5
  61. #define TOKEN_WINDOW_HIGH        8
  62. #define LINE_SWEEP_COLUMN_HIGH        6
  63. #define LINE_ENDPOINT_WINDOW_HIGH    12.0
  64.  
  65. #define DEFAULT_LINE_SUPPORT_MEDIUM    0.7
  66. #define TOKEN_SUPPORT_MEDIUM        0.7
  67. #define TOKEN_WINDOW_MEDIUM        4
  68.  
  69. #define DEFAULT_ANGLE_THRESH_LOW    0.05 /* 2.8 degrees */
  70. #define DEFAULT_LINE_SUPPORT_LOW    0.9
  71. #define TOKEN_SUPPORT_LOW        0.75
  72. #define TOKEN_WINDOW_LOW        1
  73. #define LINE_SWEEP_COLUMN_LOW        3
  74. #define LINE_ENDPOINT_WINDOW_LOW    1.0
  75.  
  76.  
  77. #define DEFAULT_SEARCH_ANGLE    0.001
  78. #define DEFAULT_ANGLE_THRESH    0.098
  79.  
  80.  
  81. #define LINE_SEARCH_DIST     500
  82.  
  83.  
  84.  
  85. #define XPOS        103
  86. #define YPOS        104
  87. #define AXIS1        105
  88. #define AXIS2        106
  89.  
  90.  
  91. #define X        1
  92. #define Y        2
  93.  
  94. #define OPEN        0
  95. #define CLOSED        1
  96.  
  97.  
  98. extern c_handle        image_trans;
  99. extern c_handle        view_trans;
  100.  
  101. double            ANGLE_THRESH;    
  102. double            LINE_ENDPOINT_WINDOW;
  103. int             CONSTRAIN;
  104. int            K_CYCLES;
  105. int            LINE_SWEEP_COLUMN;
  106. double             SEARCH_ANGLE;
  107. double             MIN_LINE_SUPPORT;
  108. double             TOKEN_SUPPORT;
  109. double             TOKEN_WINDOW;
  110.  
  111. double             MIN_ROOF_HEIGHT;
  112. double             MAX_ROOF_HEIGHT;
  113.  
  114. int xstart, ystart, xstop, ystop;
  115.  
  116. typedef double  mat_4x4[4][4];
  117. typedef double  mat_4x1[4];
  118.  
  119. typedef struct e {
  120.     float confidence;
  121.         int type;
  122.     struct l *vertex;
  123.     struct e *next;
  124.     int position;
  125.     int dir;
  126. } edgeList;
  127.  
  128. typedef struct co {
  129.     int color;
  130.     struct co *next;
  131. } colorList;
  132.  
  133. typedef struct l {
  134.     int magnitude;
  135.     colorList *colors;
  136.     long int P;  /* Polygon bit set. */
  137.         int depth;
  138.     edgeList *eList;
  139.     int x;
  140.     int y;
  141.     double xpos,ypos;
  142.     double leg1Dx, leg1Dy;
  143.     double leg2Dx, leg2Dy;
  144.         int x_corr;
  145.         int y_corr;
  146.     double height;
  147.     struct l *next;
  148.     struct l *last;
  149. } cList; 
  150.  
  151. /* as backlist for the coloring */
  152. typedef struct vl {
  153.     cList *vertex;
  154.         double confidence;
  155.         struct vl *next;
  156. } vertexList;
  157.  
  158. typedef struct MGv {
  159.         vertexList *vList;
  160.     struct MGe *eList;
  161.         int color;
  162.         double confidence;
  163.         int isscolor;
  164.     struct MGv *next;
  165. } MGvertex;
  166.  
  167. typedef struct MGe {
  168.     MGvertex *vertex;
  169.     struct MGe *next;
  170. } MGedgeList;
  171.  
  172. typedef struct MGvList {
  173.     double confidence;
  174.     MGedgeList *eList;
  175.     struct MGvList *next;
  176. } MGvertexList;
  177.  
  178. typedef struct line_node {
  179.     double x1;
  180.     double y1;
  181.     double x2;
  182.     double y2;
  183.     double contrast;
  184.     double height;
  185.     double confidence;
  186.     struct line_node *next;
  187. } line;
  188.  
  189. typedef struct {
  190.       double   x;
  191.           double   x_corr;
  192.       double   y;
  193.           double   y_corr;
  194.       double   z;
  195.       double   r;
  196. } Point;
  197.  
  198. typedef struct chain {
  199.     float chainCertainty;
  200.     int label;
  201.     int class;
  202.     int chain[MAXCHAINLEN];
  203.     struct chain *next;
  204. } pChain;
  205.  
  206. typedef struct {
  207.         int x;
  208.         int y;
  209. } vArray;
  210.  
  211. typedef double RotMatrix[4][4];
  212.  
  213. int xdim;    /** Global value of the width of the image **/
  214. int ydim;
  215. cList  *corner_list;
  216. line   *line_list;
  217.  
  218. int thresh;
  219. int cornerMax;
  220.  
  221. c_handle     in_pane;    /** Global Pane for polygon detector **/
  222. c_handle    projectionMat;
  223.  
  224. /********* RCDE Defs for image manipulation, etc.. *******************/
  225.  
  226. extern c_handle make_image();
  227. extern c_handle copy_image();
  228. extern c_handle push_image();
  229. extern c_handle_1_int_3* pick_a_pane();
  230.  
  231. struct c_handle_1_int_3* pane_choice;
  232. struct c_handle_1_int_2* image_choice;
  233. c_handle in_image, in_pane, out_pane, icopy, pane;
  234.  
  235. struct double_3* sun_vector();
  236.  
  237.  
  238. /******* Global Procedure Defs ***************************************/
  239.  
  240. double tokenSupport(cList *c1, cList *c2);
  241. double virtualTokenSupport(Point p, cList *c2);
  242.  
  243. void process_region(char *corners, char *lines, c_handle image);
  244.  
  245. void setup_defaults(double sensitivity);
  246.  
  247. int compute_intersections_region(char *lines, char *corners, 
  248.      c_handle pane, c_handle image, int x1, int y1,int x2, int y2);
  249.  
  250. void intersect_point(line l1, line l2, double_2 *result);
  251.  
  252. void computeParms(double_2 vert, line l1, line l2, double parms[2]);
  253. cList *read_corners_from_file(char *file);
  254. cList *create_list(int x, int y, double h, int mag, double l1X,
  255.             double l1Y, double l2X, double l2Y);
  256. cList *insert(cList *list, cList *ptr, int x, int y, double h, int mag,
  257.          double l1X, double l1Y, double l2X, double l2Y);
  258. void insert_end(cList *ptr, int x, int y, double h, int mag,
  259.          double l1X, double l1Y, double l2X, double l2Y);
  260. cList *insert_corner(cList *list,int x,int y, double h, int mag,
  261.          double l1X, double l1Y, double l2X, double l2Y);
  262. void print_corner_list(cList *ptr);
  263. void clear_image(c_handle image, int x1, int x2, int y1, int y2);
  264.  
  265. line *load_line_data(int startx, int starty, int stopx, int stopy,char *file,
  266.                                c_handle im);
  267. cList *sortList(cList *list);
  268. void free_list(cList *list);
  269. void free_line_list(line *list);
  270.  
  271. double distance(double x1, double y1, double x2, double y2);
  272. void labelPoly(cList *ptr, int label);
  273.  
  274.  
  275. int even(int x);
  276. void free_pChains(pChain *c);
  277. double support_val(c_handle im, cList *ptr, int *axis, int x2, int y2,
  278.              float Dx, float Dy, int *pos, int virt);
  279. float enoughSupport(c_handle im, cList *c1, cList *c2, int axis, int *pos, int *dir);
  280. int buildEdges(cList *ptr, cList *list, c_handle im, c_handle pane);
  281. void buildGraph(cList *list, c_handle im, c_handle pane);
  282. double idealX(int Dx, int Dy, RotMatrix Forward, RotMatrix Back);
  283. double idealY(int Dx, int Dy, RotMatrix Forward, RotMatrix Back);
  284. int cornerMatches(cList *c1, cList *c2, int axis);
  285.  
  286. double myatan(double y, double x);
  287. void tours(c_handle im,cList *v_list,int *curr_color,MGvertex **meta_graph);
  288. void virtualTours(c_handle im, cList *v_list, int *curr_color, 
  289.                             MGvertex **meta_graph);
  290. int virtual_dfs(c_handle im, cList *list, int axis, int color, vertexList **visited_list, cList **graph, MGvertex **meta_graph, int depth);
  291.      
  292. void build_dependency_graph(cList *v_list, int color_no, MGvertex *meta_graph);
  293. MGvertexList *indep_subset_list(MGvertex *graph);
  294. MGvertexList *get_max_iss(MGvertexList *vertex_list);
  295. MGvertexList *all_indep_subsets(MGvertex *graph);
  296. double virtualSupport(c_handle im, Point *feature,
  297.                  cList *vert1, int axis, cList *vert2, int *dir);
  298. Point featureGap(cList *vertex, int axis, cList *corner);
  299.  
  300. Point TfeatureGap(cList *v1, int axis, cList *v2);
  301.  
  302.  
  303. void project_3d_to_2d(char *image, double point[4],
  304.                                    double res_point[4]);
  305. void project_2d_to_3d(char *image, double point[4],
  306.                                    double res_point[4]);
  307. void project_2d_to_KP(char *image, double point[4], double res_point[4]);
  308.  
  309. double aref_2D_double(c_handle matrix, int i, int j);
  310. double aref_1D_double(c_handle matrix, int i);
  311. void
  312. calc_next(char *image, int axis, int type, int u, int v, float *dx, float *dy);
  313. int
  314. buildEdge(cList *v1, cList *v2, float str, int axis, c_handle pane, int pos, int dir);
  315.  
  316. int conflictIntersection(int x1, int y1, int x2, int y2);
  317.  
  318.  
  319. char *get2_5dlineFile(c_handle image);
  320. char *get2dlineFile(c_handle image);
  321. char *getTempDir(c_handle image);
  322.  
  323.  
  324.  
  325. double perfectX(cList *c1, cList *c2);
  326. double perfectY(cList *c1, cList *c2);
  327. double transLine(int line, cList *c1);
  328. void write_corners_to_file(char *fname, cList *ptr);
  329. int sum_at(c_handle im, int x1, int y1);
  330. int sqsum_at(c_handle im, int x1, int y1);
  331. void setupGridRotation(double f, double b);
  332.  
  333.  
  334. double angleBetween(line l1, line l2);
  335. float IntersectLines(line l1, line l2, double p[2]);
  336. int linesProximate(line l1, line l2);
  337. int linesOverlap(line l1, line l2);
  338.  
  339. double lineOverlaps(line l1, line l2);
  340.  
  341. double distancePointLine(Point p, line l);
  342. double distancePointLineHessian(Point p, line l);
  343. double LineLength(double StartCol, double StartRow, double EndCol, double EndRow);
  344.  
  345. void getParametricPoint(line l, double t, Point *p);
  346.  
  347.  
  348.  
  349.  
  350. int LineSegColIntercept(double StartCol,
  351.                        double StartRow,
  352.                       double  EndCol,
  353.                        double EndRow,
  354.                        double *ColIntercept);
  355.  
  356. int LineSegRowIntercept(double StartCol,
  357.                        double StartRow,
  358.                        double EndCol,
  359.                        double EndRow,
  360.                        double *RowIntercept);
  361.  
  362. double PtLinePerpDistance( double PtCol,
  363.                            double PtRow,
  364.                            double ColIntercept,
  365.                            double RowIntercept,
  366.                            double Theta);
  367.  
  368. int PtLinePerpIntercept(double PtCol,
  369.                         double PtRow,
  370.                         double ColIntercept,
  371.                         double RowIntercept,
  372.                         double Theta,
  373.                         double *InterceptPtCol,
  374.                         double *InterceptPtRow);
  375.  
  376. double LineSegTheta(double StartCol,
  377.                     double StartRow,
  378.                     double EndCol,
  379.                     double EndRow);
  380.  
  381.  
  382. int  CheckPtParlLineSeg(double PtCol,
  383.                         double PtRow,
  384.                         double LengthParlVar,
  385.                         double LengthPerpVar,
  386.                         double Length,
  387.                         double Theta,
  388.                         double StartCol,
  389.                         double StartRow,
  390.                         double EndCol,
  391.                         double EndRow);
  392.  
  393. double projectAngle(char *image, double a);
  394.  
  395. int IntersectType(double t, double s);
  396.  
  397. float **matrix(int nrl,int nrh,int ncl,int nch);
  398. float *vector(int nl,int nh);
  399. void Local_ludcmp(float **a,int n,int *indx,float *d);
  400. void Local_lubksb(float **a,int n,int *indx,float b[]);
  401. void Local_free_vector(float *v,int nl,int nh);
  402. void Local_free_matrix(float **m,int nrl,int nrh,int ncl,int nch);
  403.  
  404.  
  405. int linkedByEdge(cList *p1, cList *p2);
  406.  
  407. double image_line_support(int c_handle, double x1, double y1,
  408.               double x2, double y2, double col, 
  409.               double percentage);
  410.  
  411. MGvertexList *sort_top_K_nodes(MGvertex *meta_graph, int k);
  412. MGvertex *get_max_MG(MGvertex *graph, double max, double *new);
  413.