UNM Scheme: Boldt Line Finder

```
(make-line <number x₀> <number y₀> <number x₁> <number y₁> . <number contrast>)
```
Given <number x₀>, <number y₀>, <number x₁>, <number y₁>, i.e., the x and y locations of a line segment's initial and terminal endpoints, make-line returns a <sexpr> of type <line>. make-line takes an optional argument, <number contrast>, which can be used to specify the difference in brightness between the line's right and left sides, where right and left are defined relative to the vector, [x₁ - x₀ , y₁ - y₀]^T. Following Boldt et al., the initial and terminal endpoints should be chosen so that contrast is positive, i.e., the darker region lies to the left. If <number contrast> is not specified, contrast is set to zero. For example, > (make-line 0.0 0.0 1.0 1.0) #<line: x0 = 0 y0 = 0 x1 = 1 y1 = 1> >
Returns #t if <sexpr> is of type <line> and #f otherwise. For example,
Returns the x location of <line>'s initial endpoint. For example,
Returns the y location of <line>'s initial endpoint.
Returns the x location of <line>'s terminal endpoint.
Returns the y location of <line>'s terminal endpoint.
Returns the contrast of <line>. For example,
The procedure, make-sketch, takes a pair of integers, <number rows> and <number cols>, and a <list> of lines and returns a <sexpr> of type <sketch>. A sketch consists of a set of lines and a pair of integers, rows and cols, which specify the size of the window in which the lines will be displayed. Display happens automatically (as a side-effect) when a Scheme expression evaluates to a value of type <sketch> at the top-level. For example, returns a value of type <sketch> and causes the following window to be displayed:
Returns #t if <sexpr> is of type <sketch> and #f otherwise. For example,
Returns the row size of <sketch>. For example,
Returns the column size of <sketch>.
Returns a <list> containing the lines in <sketch>. For example,
Returns the number of lines in <sketch>. For example,
Returns a new sketch consisting of the union of lines in <sketch 1> and <sketch 2>. The row and column sizes of <sketch 1> and <sketch 2> must be the same. For example,
Given an <image>, returns a <sketch> consisting of lines representing the zero crossings of the image convolved with a Laplacian mask. The lines are computed using one of two methods. The method is specified by the value of <number>. If <number> is zero (the default value), the line is defined so that it's endpoints connect two points of the zero crossing contour localized to sub-pixel accuracy along pixel boundaries using linear interpolation. Consequently, the lines vary in length. For example,

displays the following sketch:

In the method used by Boldt et al. (specified by setting <number> equal to one), the midpoints of the lines are the same as those computed using the above method. However, the lines are all of uniform length (one) and have orientation normal to the image gradient direction at the line's midpoint (estimated by bilinearly interpolating the convolutions of the image with horizontal and vertical Sobel masks). For example,

displays the following sketch:

In both methods, a zero crossing's contrast is defined to be the image gradient magnitude at the line's midpoint. Lines' contrasts are displayed using a hot color map.
This is a procedure which a casual user won't call directly but will call instead through the main line grouping procedure, boldt. po-link! side-effects <sketch> so that it contains an adjacency-list representation of the link-graph, which is a relation on line endpoints (see Boldt et al.). The link-parameters are stored in <vector>, which must be of length seven. For example, to create the link-graph for the sketch representing the zero crossings of the chimney image, one would type the following commands:
This procedure exists primarily for debugging purposes. It takes a <sketch> as argument and displays a graphical representation of the link-graph associated with that sketch. Lines are displayed blue and links are displayed as small white semi-circles joining line endpoints. For example, generates the following display:
Like po-link!, the procedure po-replace! is called by boldt. po-replace! visits the lines in <sketch> in an unspecified order. It enumerates all paths in the link-graph which contain a line and lie within a circle of replace radius centered on the line's midpoint. Lines belonging to paths which are straight enough are replaced by new lines representing the entire straight path (see Boldt et al.). po-replace! takes a <sketch> as its first argument and a <vector> of replace-parameters as its second argument. Replaced lines in <sketch> are marked replaced and the age of all other lines is incremented by one. The return value of po-replace! is a new sketch, containing a mixture of new and unreplaced lines.
Another procedure which is called by boldt. The arguments of po-merge! are a sequence of sketches produced by repeated application of po-link! and po-replace!. Beginning with <sketch 1>, po-merge! does a fold right, copying all unreplaced (and previously unmerged) lines from <sketch 2>...<sketch N> into <sketch 1>. The return value is <sketch 1>, which now contains straight lines of all scales.
Given <number i>, returns a vector containing the link-parameters found in row i of the link-schedule. This vector is intended for use as the second argument of po-link!. For example,
Given <number i>, returns a vector containing the replace-parameters found in row i of the replace-schedule. This vector is intended for use as the second argument of po-replace!. For example,
Given an image in ASCII .pgm format specified by <string filename>, and an integer <number n>, returns a <sketch> representing the merged output of n iterations of the method for grouping straight lines described by Boldt et al.
```
(filter-on-contrast <sketch> <number c_min> . <number c_max>)
```
Returns a new sketch consisting of lines from <sketch> with contrast greater than <number c_min>. If the optional argument is also specified, then the lines must also have contrast less than <number c_max>. > (set-image-scale! 2.0) > (read-image "amroad16.pgm") #<image: rows = 256 cols = 256> >

> (define road-lines (boldt "amroad16.pgm")) > (filter-on-contrast road-lines 5.0) #<sketch: rows = 256 cols = 256 count = 8008> >
```
(filter-on-length <sketch> <number l_min> . <number l_max>)
```
Returns a new sketch consisting of lines from <sketch> with length greater than <number l_min>. If the optional argument is also specified, then the lines must also have length less than <number l_max>. > (set-image-scale! 2.0) > (read-image "im1i8.pgm") #<image: rows = 256 cols = 256> >

> (define house-lines (boldt "im1i8.pgm")) > (filter-on-length house-lines 2.0) #<sketch: rows = 256 cols = 256 count = 2997> >
The procedure sketch->postscript renders the <sketch> as a Postscript file with filename <string filename>.
The procedure write-sketch writes an ASCII representation of the <sketch> to a file with filename <string filename>. The first line of the file contains the row size and the column size separated by a space. The remaining lines of the file represent the lines of the sketch. Each line consists of x₀, y₀, x₁, y₁, and contrast for a single line separated by tab characters. For example, creates a file which looks like this:
The procedure read-sketch reads an ASCII representation of a <sketch> from the file with filename <string filename>. The first line of the file should contain the row size and the column size separated by a space. The remaining lines of the file represent the lines of the sketch. Each line should consist of x₀, y₀, x₁, y₁, and contrast for a single line separated by tab characters.

References

Boldt, M., Weiss, R., and Riseman, E.M., Token-Based Extraction of Straight Lines, IEEE Trans. on Systems, Man, and Cybernetics 19(6), Nov./Dec. 1989, pp. 1581-1594.