Photo location guessing game in Go
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.
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.
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.
Listing 2
photoset.go
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].
Listing 3
image.go
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.
Listing 4
gps.go
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.
« Previous 1 2 3 4 Next »
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.
News
-
So Long Neofetch and Thanks for the Info
Today is a day that every Linux user who enjoys bragging about their system(s) will mourn, as Neofetch has come to an end.
-
Ubuntu 24.04 Comes with a “Flaw"
If you're thinking you might want to upgrade from your current Ubuntu release to the latest, there's something you might want to consider before doing so.
-
Canonical Releases Ubuntu 24.04
After a brief pause because of the XZ vulnerability, Ubuntu 24.04 is now available for install.
-
Linux Servers Targeted by Akira Ransomware
A group of bad actors who have already extorted $42 million have their sights set on the Linux platform.
-
TUXEDO Computers Unveils Linux Laptop Featuring AMD Ryzen CPU
This latest release is the first laptop to include the new CPU from Ryzen and Linux preinstalled.
-
XZ Gets the All-Clear
The back door xz vulnerability has been officially reverted for Fedora 40 and versions 38 and 39 were never affected.
-
Canonical Collaborates with Qualcomm on New Venture
This new joint effort is geared toward bringing Ubuntu and Ubuntu Core to Qualcomm-powered devices.
-
Kodi 21.0 Open-Source Entertainment Hub Released
After a year of development, the award-winning Kodi cross-platform, media center software is now available with many new additions and improvements.
-
Linux Usage Increases in Two Key Areas
If market share is your thing, you'll be happy to know that Linux is on the rise in two areas that, if they keep climbing, could have serious meaning for Linux's future.
-
Vulnerability Discovered in xz Libraries
An urgent alert for Fedora 40 has been posted and users should pay attention.