Representing Images as Lists of Spots

As we've said a few times, computer scientists study the algorithms we write to manipulate information and the ways in which we represent information. Since an emphasis of this course is images, we have been emphasizing kinds of data related to images. You've probably noticed that we have a number of ways to algorithmically describe images. That is, we can describe images in terms of a sequence of GIMP commands, in terms of a sequence of turtle commands, as a drawing built from the unit drawings, or as a function from positions to colors.

It's now time to consider another way to think about images. As you may recall, when we first discussed ways to describe images, we talked about images as collections of colored pixels. Clearly, for really big images, it may be unwieldy to describe each and every pixel on the screen, but if the image contains just a few swatches of color on a white background, this may be an appropriate representation. (In fact, most images are represented, or at least described, in terms of lots and lots of pixels, so the technique is not just appropriate for images with a little color.) For each pixel, we'll keep track of the column, row, and color. In this class, we call this combination a spot.

While it may be difficult to describe an image only in terms of spots, the representation can be useful for small stamps, images that you want to repat over and over again. For example, here is a small stamp.

And here is the same stamp, rendered on an image. (You may need to get out your magnifying glass to see it.)

And the same stamp, rendered repeatedly and in different colors.

And the same stamp, scaled by a factor of 10, and with each spot rendered as a circle.

How will we deal with spots and stamps? In the past, we've relied on other people to implement the data types we use. This time, we're going to try to implement the types ourselves. That means we will need (a) a way to represent individual spots, (b) a way to represent stamps (essentially, collections of spots), and (c) an appropriate collection of procedures to manipulate both spots and stamps.

Fortunately, Scheme, like Lisp before it, provides a simple and elegant way to represent collections of data, the list. In contrast to Scheme's “unstructured” data types, such as symbols and numbers, lists are “structures” that contain other values as elements. In particular, a list is an ordered collection of values. In Scheme, lists can be heterogeneous, in that they may contain different kinds of values.

As we will see throughout this semester, lists provide a simple, relatively convenient, and elegant mechanism for organizing collections of information.

How does Scheme show you that something is a list? It surrounds the list with parentheses and separates the items with spaces. For example, the following is a list of three color names that we like.

("red" "grey" "black")

It's fairly clear how we'll represent a collection of spots (that is, a stamp): We'll just make a list of all the spots in the collection. (In fact, most of the time Scheme programmers want to represent collections, they end up using lists, at least during initial development.)

How do we represent each spot? Well, a spot is a combination of a column, row, and color. We can represent that with another list. For example, here is the list that might correspond to “a green spot at position (10,11)”.

(10 11 "green")

Similarly, here is a list that might represent red spots at (10,1), (10,2), and (10,3); grey spots at (11,2), (11,3), and (11,4), and black spots at (12,3), (12,4), and (12,5). Note that black seems to be represented by 255, grey by "grey", and red by "red".

((10 1 "red") (10 2 "red") (10 3 "red")
 (11 2 "grey") (11 3 "grey") (11 4 "grey")
 (12 3 "black") (12 4 "black") (12 5 "black"))

Of course, to achieve the goal of usefully representing images as lists of spots, we need to know more than what those lists might look like when printed. We must also know basic operations we can use for processing those lists, and others. These include operations for creating lists, for extracting information from lists, for extending lists, and for dealing with each element in a list.

The easiest way to create a list is to invoke a procedure named list. This procedure takes as many parameters as you care to give it and packs them together into a list. Just as the addition procedure + sums its arguments and returns the result, so the list procedure collects its arguments and returns the resulting list:

> (list "red" "grey" "black" "white")
("red" "grey" "black" "white")
> (list)
()
> (list 1 2 3 4 5 6 7)
(1 2 3 4 5 6 7)
> (list "red" 1 'red)
("red" 1 red)
> (list 10 11 (* 10 11))
(10 11 110)
> (list (list 10 1 "red") 
        (list 10 2 "red") 
        (list 10 3 "red") 
        (list 11 2 "grey") 
        (list 12 3 "grey"))
((10 1 "red")
 (10 2 "red")
 (10 3 "red")
 (11 2 "grey")
 (11 3 "grey"))

You may recall that we said that a list can contain any types of Scheme values. As the last two examples above suggest, lists can even contain other lists as values. The technique of placing one list inside another is called nesting lists, and is useful in a wide variety of situations.

Most typically, we nest lists when the element lists are used for a different purpose than the enclosing lists. For example, in the examples above, the element lists each represent one spot (that is, column, row, and color) and the list of elements represents a collection of spots.

We are not limited to this simple nesting. We can nest lists within lists within lists within lists, as deep as we desire to go. Not all of our nested values need to be lists. We can, for example, make lists some of whose elements are lists, some of whose elements are strings, some of whose elements are numbers, and so on and so forth.

Although list is a convenient way to build lists, the list operation is, itself, composed of other, more primitive, operations. Behind the scenes, list invokes cons once for each element of the completed list, to hook that element onto the previously created list. The cons procedure takes two parameters, a value and a list, and builds a new list by prepending the value onto the list. The prepended value is called the car of the resulting list. The previous list (that is, the list that has now had a new value added to the front) is called the cdr of the resulting list.

> (cons 5 (list 1 2 3)) 
(5 1 2 3)

Why is it called cons instead of list-prepend or something similar? Well, that's the name John McCarthy, the designer of Lisp, chose about fifty years ago. “cons” is short for construct, because cons constructs lists. (The custom of naming procedures with the basic type they operate on, a dash, and the key operation did not start until a few decades later.) The names car and cdr were chosen for very specific reasons that will not make sense for a few more weeks. For now, just accept that you're learning a bit of computer-ese.

Scheme's name for the empty list is a pair of parentheses with nothing between them: (). Most implementations of Scheme permit you to refer to that list as nil or null. A few permit you to type it verbatim. All permit you to describe the empty list by putting a single quote before the pair of parentheses.

> '()
()
> nil
()
> null
()

You will find that we prefer to use a name for that list. If sample code does not work in your version of Scheme, try inserting the following definitions.

(define nil '())
(define null '())

Note that by using cons and nil, we can build up a list of any length by starting with the empty list and repeatedly prepending a value.

> (define singleton (cons "red" null))
> singleton
("red")
> (define doubleton (cons "green" singleton))
> doubleton
("green" "red")
> (define tripleton (cons "yellow" doubleton))
> tripleton
("yellow" "green" "red")
> (cons "senior" (cons "third-year" (cons "second-year" (cons "freshling" null))))
("senior" "third-year" "second-year" "freshling")

You may note that lists built in this way seem a bit “backwards”. That is, the value we add last appears at the front, rather than at the back. However, that's simply the way cons works and, as the last example suggests, in many cases it is a quite sensible thing to do.

Note that cons is a pure function. That is, (cons val lst) changes neither val nor lst. Rather, cons builds a new list whose first element is val and whose remaining elements correspond to the elements of lst.

So far, so good. We now know how to build lists using two techniques: Using list and using a combination of cons and null. Of course, creating lists is not very useful unless we can extract the individual elements of the list.

The two most basic operations one uses to recover elements from a list are car and cdr. The car procedure takes as a parameter a non-empty list and returns the first element. The cdr procedure takes as a parameter a non-empty list and returns the remaining elements (that is, all but the first element). In a sense, car and cdr are the inverses of cons; if you think of a non-empty list as having been assembled by a call to the cons procedure, car gives you back the first argument to cons and cdr gives you back the second one.

> (define colors (cons "red" (cons "black" null)))
> colors
("red" "black")
> (car colors)
"red"
> (cdr colors)
("black")

We can, and often do, nest these calls. For example, to get the second element of a list, we first get the cdr of the list and then take the car of that result.

> (car (cdr colors))
"black"

To reduce the amount of typing necessary for the programmer, many implementations of Scheme provide procedures that combine car and cdr in various ways. For example, cadr computes the car of the cdr of a list (the second element), cddr computes the cdr of the cdr of a list (all but the first two elements), and caar computes the car of the car of a list.

> (define spots (list (list 10 1 "red") 
                      (list 10 2 "red") 
                      (list 10 3 "red") 
                      (list 11 2 "grey") 
                      (list 12 3 "grey")))
> spots
((10 1 "red") (10 2 "red") (10 3 "red") (11 2 "grey") (11 3 "grey"))
> (car spots)
(10 1 "red")
> (cadr spots)
(10 2 "red")
> (caddr spots)
(10 3 "red")
> (cadddr spots)
(11 2 "grey")
> (caar spots)
10
> (cadar spots)
1
> (caddar spots)
"red"

Scheme provides two basic predicates for checking whether a value is a list. The null? predicate checks whether a value is the empty list. The list? predicate checks whether a value is a list (empty or nonempty).

> (null? null)
#t
> (list? null)
#t
> (null? (list 1 2 3))
#f
> (list? (list 1 2 3))
#t
> (null? 5)
#f
> (list? 5)
#f

It turns out that you can build any other list procedure with just null, cons, car, cdr, null?, and some other programming techniques. Nonetheless, there are enough common operations that most programmers want to do with lists that Scheme includes them as basic operations. (That means you don't have to define them yourself.) Here are four that programmers frequently use.

> (length null)
0
> (length (list 1 2 3))
3
> (length (list (list 1 2 3)))
1

> (reverse (list "white" "grey" "black"))
("black" "grey" "white")

> (append (list "red" "green") (list "blue" "yellow"))
("red" "green" "blue" "yellow")

> (append null (list "blue" "yellow"))
("blue" "yellow")
> (append (list "red" "green") null)
("red" "green")
> (append null null)
()

> (define rainbow (list "red" "orange" "yellow" "green" "blue" "indigo" "violet"))
> (list-ref rainbow 1)
"orange"
> (list-ref rainbow 0)
"red"
> (list-ref rainbow 5)
"indigo"
> (list-ref rainbow 7)
list-ref: index 7 too large for list: ("red" "orange" "yellow" "green" "blue" "indigo" "violet")

We started this reading by exploring the another way to represent images, and ended up thinking about lists. Let's return to the original question. How do we use spots to represent images? We need a few more tools to deal with long lists of spots, but we can still think about individual spots.

To create a spot, we simply list the three components.

;;; Procedure:
;;;   spot-new
;;; Parameters:
;;;   col, an integer
;;;   row, an integer
;;;   color, a color (name, RGB, etc.)
;;; Purpose:
;;;   Create a new spot.
;;; Produces:
;;;   spot, a spot
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (spot-col spot) = col
;;;   (spot-row spot) = row
;;;   (spot-color spot = color
(define spot-new
  (lambda (col row color)
    (list col row color)))

Since it will be useful to extract the column, row, and color, we also write procedures that, given a spot, return the appropriate component of the spot.

;;; Procedure:
;;;   spot-row
;;; Parameters:
;;;   spot, a spot
;;; Purpose:
;;;   Extract the row from a spot.
;;; Produces:
;;;   row, an integer
(define spot-row
  (lambda (spot)
    (cadr spot)))

;;; Procedure:
;;;   spot-col
;;; Parameters:
;;;   spot, a spot
;;; Purpose:
;;;   Extract the col from a spot.
;;; Produces:
;;;   col, an integer
(define spot-col
  (lambda (spot)
    (car spot)))

;;; Procedure:
;;;   spot-color
;;; Parameters:
;;;   spot, a spot
;;; Purpose:
;;;   Extract the color from a spot.
;;; Produces:
;;;   color, an integer
(define spot-color
  (lambda (spot)
    (caddr spot)))

Why don't we just use list, car, cadr, and caddr directly? Because we want to encapsulate our data. If we decide tomorrow (or next week or next year) to change the way we implement spots, we only need to change these four procedures, rather than every single procedure that uses spots.

Of course, the spots we've just described aren't much use unless we can render them on an image. There are a number of techniques we can use. For now, let's just select a small rectangle around the spot and fill it.

;;; Procedure:
;;;   image-render-spot!
;;; Parameters:
;;;   image, an image
;;;   spot, a spot
;;; Purpose:
;;    Draw the spot on the image.
;;; Produces:
;;;   [Nothing; Called for the side effect]
(define image-render-spot!
  (lambda (image spot)
    (context-set-fgcolor! (spot-color spot))
    (image-select-rectangle! image REPLACE
                             (spot-col spot) (spot-row spot) 1 1)
    (image-fill-selection! image)
    (image-select-nothing! image)))

We also might think about rendering the spot with some enlargement factor. For larger spots, we might use circles, rather than rectangles, to render. If we're scaling the size of the spot, we probably also want to scale the position. The following provides an initial approach, but you might find others useful, too.

;;; Procedure:
;;;   image-scaled-render-spot!
;;; Parameters:
;;;   image, an image
;;;   spot, a spot
;;;   factor, a number
;;; Purpose:
;;    Draw the spot on the image, scaled by a factor of factor.
;;; Produces:
;;;   [Nothing; Called for the side effect]
;;; Preconditions:
;;;   factor >= 1
;;;   The position of the scaled spot is within the bounds of the image.
;;; Postconditions:
;;;   The image now contains a rendering of the spot.
(define image-scaled-render-spot!
  (lambda (image spot factor)
    (context-set-fgcolor! (spot-color spot))
    (image-select-ellipse! image REPLACE
                             (* factor (spot-col spot))
                             (* factor (spot-row spot))
                             factor factor)
    (image-fill-selection! image)
    (image-select-nothing! image)))

How might you change the approach? As written, the circles start at the scaled position. You might want them centered at that position. You might also find that the circles work and look better if they overlap a bit, which means that we might use more than factor for width and height.

Now, let's steal an idea from the drawings-as-values model and think about the ways in which we might transform a single spot. It doesn't make a lot of sense to scale a spot (we'll just use the enlarged render procedure mentioned above). It does, however, make sense to shift a spot horizontally or vertically or to recolor it.

Let's start with the simplest shift to a spot, which we'll call “nudging” the spot. To nudge a spot right, we add one to the column. To nudge a spot left, we subtract one. To nudge a spot up, we subtract one from the row. And, to nudge a spot down, we add one to the row. Let's look at two examples.

(define spot-nudge-right
  (lambda (spot)
    (spot-new (+ (spot-col spot) 1) (spot-row spot) (spot-color spot))))

(define spot-nudge-up
  (lambda (spot)
    (spot-new (spot-col spot) (- (spot-row spot) 1) (spot-color spot))))