Spoiled for Choice

It is not particularly difficult to select a dozen pictures at random from a photo collection of several thousand images. What is trickier is to make sure that the locations of the photos in one round of the game are not too close to each other. Many cell phone photos are taken at home, and the prospect of navigating inch by inch between the living room, balcony, and kitchen is not exactly thrilling.

Instead, I wanted the algorithm to randomly select images, while ensuring that new exciting game scenarios are created in each round, by always presenting a good mix of different regions. The cell phone photo app's geographical view in Figure 8 illustrates how the shots can be assigned to bundled hotspots based on the GPS data. The algorithm then only ever selects one image from a given hotspot.

Figure 8: Geo-clustering of photos on my cell phone.

The k-means algorithm [3] is a massive help here; k-means is an artificial intelligence [4] method, applied to cluster information in unsupervised learning [5] (Figure 9). From a set of more or less randomly distributed points in a two- or multidimensional space, k-means determines the centers of the clusters. In the Schnitzle game, these would be locations where many cell phone photos were taken, such as at home or at various vacation destinations. The algorithm then randomly selects one image only from each of these clusters. This ensures that there will be a meaningful distance between the locations where the individual pictures were taken for each round of the game.

Figure 9: The kmeans library for Go on GitHub.

The photoSet() function starting in line 18 of Listing 2 has the task of delivering an array slice of six photos of the Photo type for a new game. Line 12 defines the Photo data structure, which contains Path for the path to the image file for one thing. On top of that, it holds the geo-coordinates read from the Exif information as Lng (longitude)and Lat (latitude), both represented as 64-bit floating-point numbers.

01 package main
02
03 import (
04   "database/sql"
05   "fmt"
06   _ "github.com/mattn/go-sqlite3"
07   "github.com/muesli/clusters"
08   "github.com/muesli/kmeans"
09   "math/rand"
10 )
11
12 type Photo struct {
13   Path string
14   Lat  float64
15   Lng  float64
16 }
17
18 func photoSet() ([]Photo, error) {
19   db, err := sql.Open("sqlite3", "photos.db")
20   panicOnErr(err)
21   photos := []Photo{}
22
23   query := fmt.Sprintf("SELECT path, lat, long FROM files")
24   stmt, _ := db.Prepare(query)
25
26   rows, err := stmt.Query()
27   panicOnErr(err)
28
29   var d clusters.Observations
30   lookup := map[string]Photo{}
31
32   keyfmt := func(lat, lng float64) string {
33     return fmt.Sprintf("%f-%f", lat, lng)
34   }
35
36   for rows.Next() {
37     var path string
38     var lat, lng float64
39     err = rows.Scan(&path, &lat, &lng)
40     panicOnErr(err)
41     lookup[keyfmt(lat, lng)] = Photo{Path: path, Lat: lat, Lng: lng}
42     d = append(d, clusters.Coordinates{
43       lat,
44       lng,
45     })
46   }
47
48   db.Close()
49
50   maxClusters := 6
51   km := kmeans.New()
52   clusters, err := km.Partition(d, 10)
53   panicOnErr(err)
54
55   rand.Shuffle(len(clusters), func(i, j int) {
56     clusters[i], clusters[j] = clusters[j], clusters[i]
57   })
58
59   for _, c := range clusters {
60     if len(c.Observations) < 3 {
61       continue
62     }
63     rndIdx := rand.Intn(len(c.Observations))
64     coords := c.Observations[rndIdx].Coordinates()
65     key := keyfmt(coords[0], coords[1])
66     photo := lookup[key]
67     photos = append(photos, photo)
68     if len(photos) == maxClusters {
69       break
70     }
71   }
72   return photos, nil
73 }
74
75 func randPickExcept(pick []Photo, notIdx int) int {
76   idx := rand.Intn(len(pick)-1) + 1
77   if idx == notIdx {
78     idx = 0
79   }
80   return idx
81 }

To do this, photoSet() connects to the previously created SQLite database photos.db starting in line 19 and runs the SELECT query starting in line 23 to sort through all the previously read photo files along with their GPS coordinates. After the for loop, which starts in line 36 and processes all the table tuples it finds, all records now exist in an array of clusters.Observations type elements, ready to be processed by the kmeans package from GitHub [6].

The call to km.Partition() then assigns the GPS coordinates to 10 different clusters. From these, line 60 then discards tiny clusters with fewer than three entries. This prevents the same photos from appearing time and time again in each game, not giving the algorithm a chance to deliver variety in the form of random selections from a specific cluster. The algorithm selects a maximum of six (maxClusters) photos from the remaining clusters and then puts them in random order with the shuffle function from the rand package.

Because the kmeans cluster library from GitHub is not familiar with photo collections, but can only sort points with X/Y coordinates, line 41 creates a lookup hash map. It maps the longitude and latitude of the photos to the JPEG images on the disk. When the algorithm comes back with the coordinates of a desired image later on, the program can find, load, and display the associated image.

Controlled Randomness

From the representatives of all the chosen clusters, the Schnitzle game initially needs to select a secret target picture for the player to guess. It then opens the game with a random starting image, but it would not be a good idea to pick the secret image, even by accident! The rand.Intn(len(<N>)) standard solution in Go delivers randomly and equally distributed index positions between   (inclusive) and len(<N>) (exclusive), thus picking purely random elements from the array.

The randPickExcept() function starting in line 75 of Listing 2 now picks a random element from the array passed into it, without ever revealing the element that resides in the notIdx space. This is accomplished by the algorithm only selecting the elements in index positions 1..<N> from the elements in the index range 0..<N>, neglecting the first image in the list. And, if the choice happens to fall on the forbidden notIdx index position, the function simply delivers the   item, which was previously excluded from the pick, as a replacement. This way, all photos, except the secret one, have an equal probability of being picked as a starting point.

Slimming Down

Listing 3 helps to load the scaled down cell phone photos into the GUI. One difficulty here is that many cell phones have the bad habit of storing image pixels in a rotated orientation when taken and noting in the header that the image needs to be rotated through 90 or 180 degrees for display purposes [7].

01 package main
02
03 import (
04   "fyne.io/fyne/v2/canvas"
05   "github.com/disintegration/imageorient"
06   "github.com/nfnt/resize"
07   "image"
08   "os"
09 )
10
11 const DspWidth = 300
12 const DspHeight = 150
13
14 func dispDim(w, h int) (dw, dh int) {
15   if w > h {
16     // landscape
17     return DspWidth, DspHeight
18   }
19   // portrait
20   return DspHeight, DspWidth
21 }
22
23 func scaleImage(img image.Image) image.Image {
24   dw, dh := dispDim(img.Bounds().Max.X,
25     img.Bounds().Max.Y)
26   return resize.Thumbnail(uint(dw),
27     uint(dh), img, resize.Lanczos3)
28 }
29
30 func showImage(img *canvas.Image, path string) {
31   nimg := loadImage(path)
32   img.Image = nimg.Image
33
34   img.FillMode = canvas.ImageFillOriginal
35   img.Refresh()
36 }
37
38 func loadImage(path string) *canvas.Image {
39   f, err := os.Open(path)
40   panicOnErr(err)
41   defer f.Close()
42   raw, _, err := imageorient.Decode(f)
43   panicOnErr(err)
44
45   img := canvas.NewImageFromResource(nil)
46   img.Image = scaleImage(raw)
47
48   return img
49 }

This quirky behavior is handled by the imageorient package that Listing 3 pulls in from GitHub in line 5, auto-rotating each image before it is handed to the GUI for display. Also, nobody really wants to move massive photos around on the screen. Instead, the nfnt/resize package (also from GitHub) creates handy thumbnails from the large photos with the help of the Thumbnail() function in line 26.

Listing 4 computes the distance between the photo shoot locations of two image files and the angle from 0 to 360 degrees at which you would have to start walking to get from A to B. As the earth isn't a flat surface, calculating these numbers isn't as easy as on a two-dimensional map, but the formulas dealing with the required 3D geometry are not too complicated and already available online [8]. In line 8, the hike() function takes the longitude (lng<N>) and latitude (lat<N>) from the GPS data of two photos and taps into the functions of the golang-geo library, including GreatCircleDistance() and BearingTo() to determine the distance and bearing to travel from one photo to the other.

01 package main
02
03 import (
04   geo "github.com/kellydunn/golang-geo"
05   "math"
06 )
07
08 func hike(lat1, lng1, lat2, lng2 float64) (float64, string, error) {
09   p1 := geo.NewPoint(lat1, lng1)
10   p2 := geo.NewPoint(lat2, lng2)
11
12   bearing := p1.BearingTo(p2)
13   dist := p1.GreatCircleDistance(p2)
14
15   names := []string{"N", "NE", "E", "SE", "S", "SW", "W", "NW", "N"}
16   idx := int(math.Round(bearing / 45.0))
17
18   if idx < 0 {
19     idx = idx + len(names)
20   }
21
22   return dist, names[idx], nil
23 }

To convert the route's bearing, available as a floating-point number ranging from 0 to 360 degrees into a compass direction such as north or northeast, line 16 divides the angle by 45, rounds the result to the nearest integer, and then accesses the array slice in line 15 with that index. Index   is N for north, 1 is NE for northeast, and so on. If the index drops below  , which can happen with negative angles, line 19 simply adds the length of the array slice to arrive at an index that addresses the array slice from the end instead.