;;; This software is being provided to you, the LICENSEE, by the
;;; Massachusetts Institute of Technology (M.I.T.), and the NEC Research
;;; Institute (NECI) under the following license.  By obtaining, using
;;; and/or copying this software, you agree that you have read,
;;; understood, and will comply with these terms and conditions:
;;; 
;;; Permission to use, copy, modify and distribute, including the right to
;;; grant others rights to distribute at any tier, this software and its
;;; documentation for research purposes only and without fee or royalty is
;;; hereby granted, provided that you agree to comply with the following
;;; copyright notice and statements, including the disclaimer, and that
;;; the same appear on ALL copies of the software and documentation,
;;; including modifications that you make for internal use or for
;;; distribution:
;;; 
;;; Copyright 1995 by the Massachusetts Institute of Technology.  All
;;; rights reserved.  Copyright 1995 by NEC Research Institute Inc. All
;;; rights reserved
;;; 
;;; THIS SOFTWARE IS PROVIDED "AS IS", AND M.I.T. and NECI MAKE NO
;;; REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.  By way of example,
;;; but not limitation, M.I.T. and NECI MAKE NO REPRESENTATIONS OR
;;; WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR PURPOSE OR
;;; THAT THE USE OF THE LICENSED SOFTWARE OR DOCUMENTATION WILL NOT
;;; INFRINGE ANY THIRD PARTY PATENTS, COPYRIGHTS, TRADEMARKS OR OTHER
;;; RIGHTS.
;;; 
;;; The name of the Massachusetts Institute of Technology or M.I.T., or
;;; NEC Research Institute, or NECI may NOT be used in advertising or
;;; publicity pertaining to distribution of the software.  Title to
;;; copyright in this software and any associated documentation shall at
;;; all times remain with M.I.T. and NECI, and USER agrees to preserve
;;; same.
;;; 

(in-package group)

;;; This file contains some sample code for running the grouping system.  It should
;;; not be loaded; rather, portions of this file may be extracted and run.

;;; To load the system, a command such as:

(LOAD "~/lisp/group/system")

;;; is executed.  "~/lisp/" should be replaced by whatever main directory the system
;;; resides in.

;;; *** Ignore starred documentation if you've ftp'ed this code.  This refers only to my
;;; *** own version of the code.  

;;; *** It will be more useful, though, to load the file "~dwj/lisp/region-matching" since
;;; *** This will also load my window system code, and functions for looking at the convex groups.
;;; *** The functions given at the bottom of this file will now be loaded, and run, and
;;; *** can be used to look at groups and select them.

;;; If you want to try to run the system using a single LISP command, because, for example,
;;; you don't hack LISP, you can use the following command:

(group:edge-file-to-convex-group-file infile outfile k :width filewidth :height fileheight)

;;; This takes a file that gives edges, in raw format, where 0 indicates no edge,
;;; and 255 indicates an edge.  The output is an ASCII file showing the convex groups
;;; found.  Each line in the file shows a line segment, there are blank lines separating
;;; the convex groups.  k indicates the salience of each group (see the paper).
;;; :width and :height should by typed just like that, whereas filewidth and fileheight
;;; are replaced by the file dimensions.

;;; Next, you should switch to the GROUP package:

(in-package group)

;;; To find convex groups, one should create a binary array as an edge map, and then
;;; run:

 (remove-duplicate-answers (CONVEX-LINES-FROM-EDGES-SPLIT *TEST-ARRAY* 0.9))

;;; Here, CONVEX-LINES-FROM-EDGES-SPLIT is the main routine which returns a list of
;;; convex groups given a binary array and a threshold, k, (see the paper for a 
;;; description of k, as well as the whole grouping system).  There is a third
;;; optional argument, which adjusts the thresholds for the split-and-merge line
;;; extractor.  The default is 1, and any other value will create a coarser approximation.
;;; 2 is a reasonable value here.

;;; remove duplicate answers removes identical convex groups.  One always wants to do this,
;;; and that should probably have been the default.

;;; Here is an example of some code that builds a test array, and finds groups:

(progn
 (defvar *test-array*)
(setq *test-array* (make-array (list 50 50) :element-type 'bit :initial-element 0))
(loop for i from 11 to 29
      doing
      (setf (aref *test-array* i 10) 1)
      (setf (aref *test-array* i 30) 1))
(loop for j from 11 to 29
      doing
      (setf (aref *test-array* 10 j) 1)
      (setf (aref *test-array* 30 j) 1))
;; This array now has a square in it.

(loop for i from 0 below 50
      doing
      (format t "~%")
      (loop for j from 0 below 50 
            doing
            (format t "~A" (aref *test-array* i j))))
(format t "~%~%")

;; This shows the array.

 (remove-duplicate-answers (CONVEX-LINES-FROM-EDGES-SPLIT *TEST-ARRAY* 0.9))
)

;;; The convex groups that get returned are structures.  If, for example, you only
;;; want the end points of the line segments that make up the convex groups, you
;;; could run:

(CONVEX-GROUP-BOUNDING-LINE-SEGMENTS cg)

;;; This is contained in the file, "group/interface.lisp", along with a bunch of other 
;;; useful routines for processing the convex groups.
;;; It returns a list of line segments that form a convex group.  These are structures as well.
;;; The points of the line segments are accessed with: line-segment-point-1, line-segment-point-2.
;;; The points are structures, accessed by point-x, and point-y.  Note that the above
;;; routine is slightly complicated, because a line segment found in the image may participate
;;; only partially in a convex group, ie. only a subset of the line might be in the group.
;;; However, if you don't look at this routine, and try to extract the line segments yourself
;;; from the convex group structure, you are liable to make a mistake.

;;; Two other useful routines in "group/interface.lisp" are:
;;; CONVEX-GROUP-INNER-POLYGON-VERTICES and
;;; CONVEX-GROUP-OUTER-POLYGON-VERTICES.  See that file for a brief description of them.

;;; Finally, you may find that the code is too slow, or bombs out altogether due to a 
;;; lack of space.  This is because both space and runtime will be quadratic in the number
;;; of lines found in the image.  The best way to deal with this is to either use a coarser
;;; straight-line approximation to the edges in the image, or to just throw away the really
;;; short lines in the image.  The algorithm will be robust to these measures because it
;;; will use only portions of lines in a single group, and because it is robust to small gaps
;;; in groups.  To try this, use the routine

(CONVEX-LINES-USING-LONGEST edges n k &optional (m 1))

;;; also found in "group/interface.lisp".  You also want to remove duplicates here.  ie, do:

(remove-duplicate-answers (CONVEX-LINES-USING-LONGEST edges n k &optional (m 1)))

;;; Here edges is a binary array of the edge map, as
;;; above.  n indicates how many lines to use from the image (the n longest are used).
;;; k is the salience threshold, as above.  And m is a paramter that determines how closely
;;; to approximate the edges.  You might try 1.5 or 2 here.

;;; In addition to the routines in interface.lisp, here are two routines that will not
;;; run because I haven't included any window interface, but which illustrate how one
;;; might look through the convex groups, picking out some of them by hand.

;;; This function, and the one below, will not run because they use the Allegro
;;; window system, and functions to access it that I have not included.  The functions
;;; are given for illustrative purposes only.  In particular, they show a couple of routines
;;; that would be useful if you wanted to implement functions like these.  When this function works, it pops
;;; up a series of images, showing the convex groups, with a simple method for
;;; the user to select a subset of them by hand.  
(defun SELECT-CONVEX-GROUP-LIST (cgs min-len image)
  (let* ((background (dotted-edge-image image 4))
         ;; dotted-edge-image takes the edge map and displays it in an array as dotted.
         (background-array (g:copy-array background))
         (window (mw:make-array-window background-array "Convex Groups"))
         ;; This window code is not included.
         (cgs (loop for cg in cgs when (< min-len (convex-group-length cg)) collect cg))
         (collection (collect-separate-convex-groups-non-recursive cgs)))
         ;; collect-separate-convex-groups-non-recursive is a useful routine that
         ;; divides a list of convex groups into a list of lists, such that each
         ;; list contains convex groups that don't overlap when they are bounded
         ;; with an axial rectangle.  That is, each list of convex groups can be
         ;; displayed in a single image, without being too confusing.  See the
         ;; paper for examples of this.
    (loop for coll in collection
          for i from 0
          for selected-cgs = (if (cg-list-selected? 
                                   coll (g::copy-into-bit-array background background-array)
                                   window)
                                 (if (null (cdr coll))
                                     coll
                                     (loop for cg in coll
                                           when (cg-list-selected? 
                                                   (list cg) 
                                                   (g:copy-into-bit-array 
                                                     background background-array)
                                                     window)
                                             collect cg into res
                                             finally (return res)))
                                 nil)
          append selected-cgs into result
          until (if (= 0 (mod i 3)) (y-or-n-p "Quit?") nil)
          finally (return result))))

;;; This routine also will not run, since it uses window code that is not included.
(defun CG-LIST-SELECTED? (cg-list image window)         
   (cw:clear window)
   (mw::display-bit-array (2dg::array-convex-groups cg-list :raster image)
         ;; 2dg::array-convex-groups is a useful function that depicts a list
         ;; of convex groups into a binary array, each with a rectangle around it.
                     :window window)
   (y-or-n-p "Select?"))


;;; *** If you loaded the region system, and want to look at groups, you should do something
;;; *** like the following:

(setq image (read-raw-canny-edges "/vision/images/regions/new_disket1.edge.raw"))
(progn (setq cgs 
             (remove-duplicate-answers 
                (CONVEX-LINES-FROM-EDGES-SPLIT image .8)))
       nil)
(reg:SELECT-CONVEX-GROUP-LIST cgs 50 image)

