This is a translation of Sau Shon Chang’s blog post. In the first half, his approach to creating photo mosaic on Go is described, and in the second half, the program is accelerated by adding competition (channels, gorutiny).

For inaccuracies of the translation, write in lichku.



A few months ago, my good friend Satish Talim suggested a great idea - to create several competitions on Go to pump Go programmers' skills. The idea of ​​the project is to come up with a programming task every month (or so), which will be a fresh and interesting challenge for the Go community. The winners will receive prizes, but more importantly, this is an attempt to help each other and myself in particular. Satish asked me to come up with a task and I came up with it with pleasure for the third competition (challenge # 3).



Being a web application programmer for most of my career, it was a natural thought to come up with a web application competition. And recently on the hackathon, I wrote a script on Ruby for generating mosaic , so I thought to combine these ideas together in the task of creating a web application for generating photo mosaic.

')





Honestly, at the time of publishing the task, my web application was not written yet. I started writing it after the competition was over. Writing a photo application for photo mosaic took me about two days. But it was not finished, because I wanted to go further and add competitiveness to Go to speed up the program. This blog post is the result of what I did.



All code from this post can be found at github.com/sausheong/mosaic . I note that the code on the githaba is slightly different from what is presented below.



The demo can be viewed at mosaic.saush.com . (Approx. Trans. - do not frighten the application with large pictures, the server is weak, so it willingly falls even with pictures in 4 MB). It is hosted on Digital Ocean using Docker via Tutum. The performance of the demo on the server is not as high as in this post, because it uses only 1 CPU VM and 512 MB.

Create photomosaic.

Photographic mosaics or photo mosaic is a picture (usually a photograph), which was divided into rectangular sections (usually of the same size), each of which is replaced by a new picture. If you look from afar or squint, then you can see the original picture. And if you look closer, we will see that the big picture actually consists of hundreds or even thousands of small tiles-pictures.



The basic idea is simple - the web application allows the user to upload the necessary image, on the basis of which a mosaic will be generated. To make it easier, I assumed that the images are preloaded in the directory and have the desired size.



Let's start with the algorithm for photo mosaic. A web application consists of simple steps and can be written without the use of third-party libraries.

1. Create a database of images, hash tiles, scanning the directory with images. Then we create a display, where the file name is the key, and the average color of the image is the value. The average color value is calculated for a tuple of 3 elements: red, green, blue (RGB), - for each pixel and adds the values ​​of all red, green and blue pixels divided by the total number of pixels. (Note: the author uses the term tuple, but Go has no tuples per se, and arrays are very similar in properties. Not to be confused with slices).
2. Cut the target image into small tiles of the desired size.
3. For each section of the target image, we calculate the average color of the upper left pixel and assume that this is the average color of the entire section.
4. We are looking for a suitable tile from the database of tiles, which best of all coincides with the average color of the corresponding section of the target image, and place it at a suitable place in photomazyk. To find the best match, we calculate the Euclidean distance between two colors [3] of the tuple by converting each color [3] of the tuple to a point in three-dimensional space.
5. Delete the found tiles from the database so that the remaining tiles remain unique.

I placed all the written code for creating a mosaic in a single file mosaic.go. Let's get acquainted with each function from this file.

//     func averageColor(img image.Image) [3]float64 { bounds := img.Bounds() r, g, b := 0.0, 0.0, 0.0 for y := bounds.Min.Y; y < bounds.Max.Y; y++ { for x := bounds.Min.X; x < bounds.Max.X; x++ { r1, g1, b1, _ := img.At(x, y).RGBA() r, g, b = r+float64(r1), g+float64(g1), b+float64(b1) } } totalPixels := float64(bounds.Max.X * bounds.Max.Y) return [3]float64{r / totalPixels, g / totalPixels, b / totalPixels} } 

We start with the averageColor function, which calculates the values ​​of all the red, green and blue pixels of the image, then sums them (separately) and divides each sum of values ​​by the total number of pixels of the image. Then we return [3] a tuple (actually an array of 3 elements) consisting of these values.



Next, look at the function to reduce the image ( resize )

 //       newWidth func resize(in image.Image, newWidth int) image.NRGBA { bounds := in.Bounds() width := bounds.Max.X - bounds.Min.X ratio := width / newWidth out := image.NewNRGBA(image.Rect(bounds.Min.X/ratio, bounds.Min.X/ratio, bounds.Max.X/ratio, bounds.Max.Y/ratio)) for y, j := bounds.Min.Y, bounds.Min.Y; y < bounds.Max.Y; y, j = y+ratio, j+1 { for x, i := bounds.Min.X, bounds.Min.X; x < bounds.Max.X; x, i = x+ratio, i+1 { r, g, b, a := in.At(x, y).RGBA() out.SetNRGBA(i, j, color.NRGBA{uint8(r), uint8(g), uint8(b), uint8(a)}) } } return *out } 

The tilesDB function creates a database of images by scanning the image directory.

 //  tilesDB   func tilesDB() map[string][3]float64 { fmt.Println("Start populating tiles db ...") db := make(map[string][3]float64) files, _ := ioutil.ReadDir("tiles") for _, f := range files { name := "tiles/" + f.Name() file, err := os.Open(name) if err == nil { img, _, err := image.Decode(file) if err == nil { db[name] = averageColor(img) } else { fmt.Println(":", err, name) } } else { fmt.Println("cannot open file", name, err) } file.Close() } fmt.Println("Finished populating tiles db.") return db } 

The tile database is a display with a string in the key and [3] a tuple (in this case, an array of three elements) in the value. I open each image file in the directory and calculate the average color of the image to fill in the display value data. The tile database is used to search for a suitable tile in the image directory. It is passed to the nearest function, along with the target color value [3] of the tuple.

 //      func nearest(target [3]float64, db *map[string][3]float64) string { var filename string smallest := 1000000.0 for k, v := range *db { dist := distance(target, v) if dist < smallest { filename, smallest = k, dist } } delete(*db, filename) return filename } 

Each value in the database is compared with the target colors, then the value with the smallest difference is returned as the most suitable tile. The value found is removed from the database. The distance function calculates the Euclidean distance between two [3] tuples.

 //       func distance(p1 [3]float64, p2 [3]float64) float64 { return math.Sqrt(sq(p2[0]-p1[0]) + sq(p2[1]-p1[1]) + sq(p2[2]-p1[2])) } //   func sq(n float64) float64 { return n * n } 

Finally, scanning and loading a database of tiles when creating each photo mosaic will look awkward. I want to do this only once, and then clone this database when creating a photo mosaic. The initial tile database TILESDB is created as a global variable and is declared at the beginning of the web application.

 var TILESDB map[string][3]float64 //         func cloneTilesDB() map[string][3]float64 { db := make(map[string][3]float64) for k, v := range TILESDB { db[k] = v } return db } 

Web application photo mosaic

After preparing the functions for generating photo mosaics, you can start writing my web application. The web application will be in the source file named main.go.

 package main import ( "fmt" "html/template" "net/http" "bytes" "encoding/base64" "image" "image/draw" "image/jpeg" "os" "strconv" ) func main() { mux := http.NewServeMux() files := http.FileServer(http.Dir("public")) mux.Handle("/static/", http.StripPrefix("/static/", files)) mux.HandleFunc("/", upload) mux.HandleFunc("/mosaic ", mosaic) server := &http.Server{ Addr: "127.0.0.1:8080", Handler: mux, } //     TILESDB = tilesDB() fmt.Println("Mosaic server started.") server.ListenAndServe() } //    func upload(w http.ResponseWriter, r *http.Request) { t, _ := template.ParseFiles("upload.html") t.Execute(w, nil) } // HandlerFunc mosaic       func mosaic(w http.ResponseWriter, r *http.Request) { t0 := time.Now() //    POST  r.ParseMultipartForm(10485760) // max body in memory is 10MB file, _, _ := r.FormFile("image") defer file.Close() tileSize, _ := strconv.Atoi(r.FormValue("tile_size")) //      original, _, _ := image.Decode(file) bounds := original.Bounds() //      newimage := image.NewNRGBA(image.Rect(bounds.Min.X, bounds.Min.Y, bounds.Max.X, bounds.Max.Y)) //    db := cloneTilesDB() // source point       0, 0    sp := image.Point{0, 0} for y := bounds.Min.Y; y < bounds.Max.Y; y = y + tileSize { for x := bounds.Min.X; x < bounds.Max.X; x = x + tileSize { //        r, g, b, _ := original.At(x, y).RGBA() color := [3]float64{float64(r), float64(g), float64(b)} //      nearest := nearest(color, &db) file, err := os.Open(nearest) if err == nil { img, _, err := image.Decode(file) if err == nil { //       t := resize(img, tileSize) tile := t.SubImage(t.Bounds()) tileBounds := image.Rect(x, y, x+tileSize, y+tileSize) //     draw.Draw(newimage, tileBounds, tile, sp, draw.Src) } else { fmt.Println("error:", err, nearest) } } else { fmt.Println("error:", nearest) } file.Close() } } buf1 := new(bytes.Buffer) jpeg.Encode(buf1, original, nil) originalStr := base64.StdEncoding.EncodeToString(buf1.Bytes()) buf2 := new(bytes.Buffer) jpeg.Encode(buf2, newimage, nil) mosaic := base64.StdEncoding.EncodeToString(buf2.Bytes()) t1 := time.Now() images := map[string]string{ "original": originalStr, "mosaic": mosaic, "duration": fmt.Sprintf("%v ", t1.Sub(t0)), } t, _ := template.ParseFiles("results.html") t.Execute(w, images) } 

The basic logic of creating photo mosaic is described in the mosaic function which is a handler. First I get the downloaded file and the size of the tiles from the form.

 //    POST  r.ParseMultipartForm(10485760) //   10  file, _, _ := r.FormFile("image") defer file.Close() tileSize, _ := strconv.Atoi(r.FormValue("tile_size")) 

Next, I decode the downloaded target image and create a new image for photo mosaic.

 //      original, _, _ := image.Decode(file) bounds := original.Bounds() //      newimage := image.NewNRGBA(image.Rect(bounds.Min.X, bounds.Min.Y, bounds.Max.X, bounds.Max.Y)) 

I also clone the initial database of tiles and determine the initial points of each tile (needed further for the image / draw package)

 //    db := cloneTilesDB() // source point       0, 0    sp := image.Point{0, 0} 

Now we are ready to iterate over all the tiles of the selected size in the target image.

  for y := bounds.Min.Y; y < bounds.Max.Y; y = y + tileSize { for x := bounds.Min.X; x < bounds.Max.X; x = x + tileSize { //        r, g, b, _ := original.At(x, y).RGBA() color := [3]float64{float64(r), float64(g), float64(b)} //      nearest := nearest(color, &db) file, err := os.Open(nearest) if err == nil { img, _, err := image.Decode(file) if err == nil { //       t := resize(img, tileSize) tile := t.SubImage(t.Bounds()) tileBounds := image.Rect(x, y, x+tileSize, y+tileSize) //     draw.Draw(newimage, tileBounds, tile, sp, draw.Src) } else { fmt.Println("error:", err, nearest) } } else { fmt.Println("error:", nearest) } file.Close() } } 

For each section, select the upper left pixel and decide that this is the average color of the section. Further we look for the tile most suitable for color in a DB. Tiled DB gives the name of the file, the size of which we change to the specified. The resulting tile is placed in the mosaic (newimage) created earlier.



After the photo mosaic is created, I will re-encode it in JPEG format, and then re-encode it into base64 string.

 buf1 := new(bytes.Buffer) jpeg.Encode(buf1, original, nil) originalStr := base64.StdEncoding.EncodeToString(buf1.Bytes()) buf2 := new(bytes.Buffer) jpeg.Encode(buf2, newimage, nil) mosaic := base64.StdEncoding.EncodeToString(buf2.Bytes()) t1 := time.Now() images := map[string]string{ "original": originalStr, "mosaic": mosaic, "duration": fmt.Sprintf("%v ", t1.Sub(t0)), } t, _ := template.ParseFiles("results.html") t.Execute(w, images) 

The original target image and photo mosaic are sent to the results.html template for display on the next page. As you can see, the picture is displayed in the data URL as embedded base64 content directly on the web page.

 <!DOCTYPE html> <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> <title>Mosaic</title> ... </head> <body> <div class='container'> <div class="col-md-6"> <img src="data:image/jpg;base64,{{ .original }}" width="100%"> <div class="lead">Original</div> </div> <div class="col-md-6"> <img src="data:image/jpg;base64,{{ .mosaic }}" width="100%"> <div class="lead">Mosaic – {{ .duration }} </div> </div> <div class="col-md-12 center"> <a class="btn btn-lg btn-info" href="/">Go Back</a> </div> </div> <br> </body> </html> 

Screenshot of the created mosaic:



Basic photomosaic



Now that we have a basic web application for generating photo mosaic, let's add a version with lightweight streams and simultaneous execution of functions.

Competitive web application photo mosaic

One of the most frequent tasks in using competitiveness is improving performance. The web application I wrote creates a photo mosaic from a 151 KB JPEG image in 2.25 seconds. The speed does not hit and can definitely be improved by adding lightweight streams. In this example, I will use a fairly simple algorithm for simultaneous execution of gorutin.

1. We divide the original image into 4 parts
2. We process them simultaneously
3. We combine the result back into one mosaic

This can be represented in this form:



Competitive algorithm



I note that this is not the only way to improve performance using lightweight streams, but it is the only simple and direct way.



The only function that we will change is the mosaic handler. Previously, we had the only handler for creating photo mosaic. In the competitive version of the web application, photo mosaic needs to be divided into two new functions that will divide ( cut ) and combine ( combine ) a picture. We will call cut and combine from the mosaic function.

 func mosaic(w http.ResponseWriter, r *http.Request) { t0 := time.Now() r.ParseMultipartForm(10485760) //   10  file, _, _ := r.FormFile("image") defer file.Close() tileSize, _ := strconv.Atoi(r.FormValue("tile_size")) original, _, _ := image.Decode(file) bounds := original.Bounds() db := cloneTilesDB() //  c1 := cut(original, &db, tileSize, bounds.Min.X, bounds.Min.Y, bounds.Max.X/2, bounds.Max.Y/2) c2 := cut(original, &db, tileSize, bounds.Max.X/2, bounds.Min.Y, bounds.Max.X, bounds.Max.Y/2) c3 := cut(original, &db, tileSize, bounds.Min.X, bounds.Max.Y/2, bounds.Max.X/2, bounds.Max.Y) c4 := cut(original, &db, tileSize, bounds.Max.X/2, bounds.Max.Y/2, bounds.Max.X, bounds.Max.Y) //  c := combine(bounds, c1, c2, c3, c4) buf1 := new(bytes.Buffer) jpeg.Encode(buf1, original, nil) originalStr := base64.StdEncoding.EncodeToString(buf1.Bytes()) t1 := time.Now() images := map[string]string{ "original": originalStr, "mosaic": <-c, "duration": fmt.Sprintf("%v ", t1.Sub(t0)), } t, _ := template.ParseFiles("results.html") t.Execute(w, images) } 

The cut image is processed by the cut function.





Splitting the target image into 4 parts



The original image is cut into 4 quadrants in order to process them simultaneously.

 c1 := cut(original, &db, tileSize, bounds.Min.X, bounds.Min.Y, bounds.Max.X/2, bounds.Max.Y/2) c2 := cut(original, &db, tileSize, bounds.Max.X/2, bounds.Min.Y, bounds.Max.X, bounds.Max.Y/2) c3 := cut(original, &db, tileSize, bounds.Min.X, bounds.Max.Y/2, bounds.Max.X/2, bounds.Max.Y) c4 := cut(original, &db, tileSize, bounds.Max.X/2, bounds.Max.Y/2, bounds.Max.X, bounds.Max.Y) 

You probably noticed that these are normal functions without gorutin, how can they be performed simultaneously? The point is that the cut function internally creates an anonymous Gorutina and returns the channel.

 func cut(original image.Image, db *map[string][3]float64, tileSize, x1, y1, x2, y2 int) <-chan image.Image { c := make(chan image.Image) sp := image.Point{0, 0} go func() { newimage := image.NewNRGBA(image.Rect(x1, y1, x2, y2)) for y := y1; y < y2; y = y + tileSize { for x := x1; x < x2; x = x + tileSize { r, g, b, _ := original.At(x, y).RGBA() color := [3]float64{float64(r), float64(g), float64(b)} nearest := nearest(color, db) file, err := os.Open(nearest) if err == nil { img, _, err := image.Decode(file) if err == nil { t := resize(img, tileSize) tile := t.SubImage(t.Bounds()) tileBounds := image.Rect(x, y, x+tileSize, y+tileSize) draw.Draw(newimage, tileBounds, tile, sp, draw.Src) } else { fmt.Println("error:", err) } } else { fmt.Println("error:", nearest) } file.Close() } } c <- newimage.SubImage(newimage.Rect) }() return c } 

The logic is exactly the same as in the original web application. I create a channel in the cut function and declare an anonymous Gorutina, which sends the result of the calculations to this channel. Then return this channel. Thus, the channel is immediately returned to the mosaic handler function, and the photo mosaic segment is sent to this channel as soon as it is completely processed.



I divided the original image into 4 parts and converted them separately into a photo mosaic. It is time to put the pieces back into a single picture.

 func combine(r image.Rectangle, c1, c2, c3, c4 <-chan image.Image) <-chan string { c := make(chan string) //   go func() { var wg sync.WaitGroup img := image.NewNRGBA(r) copy := func(dst draw.Image, r image.Rectangle, src image.Image, sp image.Point) { draw.Draw(dst, r, src, sp, draw.Src) wg.Done() } wg.Add(4) var s1, s2, s3, s4 image.Image var ok1, ok2, ok3, ok4 bool for { select { case s1, ok1 = <-c1: go copy(img, s1.Bounds(), s1, image.Point{r.Min.X, r.Min.Y}) case s2, ok2 = <-c2: go copy(img, s2.Bounds(), s2, image.Point{r.Max.X / 2, r.Min.Y}) case s3, ok3 = <-c3: go copy(img, s3.Bounds(), s3, image.Point{r.Min.X, r.Max.Y/2}) case s4, ok4 = <-c4: go copy(img, s4.Bounds(), s4, image.Point{r.Max.X / 2, r.Max.Y / 2}) } if (ok1 && ok2 && ok3 && ok4) { break } } //       wg.Wait() buf2 := new(bytes.Buffer) jpeg.Encode(buf2, newimage, nil) c <- base64.StdEncoding.EncodeToString(buf2.Bytes()) }() return c } 

As in the cut function, the main logic of connecting the image is in the gorutin, and the channel is created only for receiving data.



In the anonymous Gorutina, another anonymous function has been created, with which the copy variable is assigned. This function copies the photo mosaic segment into the final mosaic. Later it will be launched as a separate gorutin, so it is impossible to know when it will be executed. To solve this problem and synchronize the execution of the copy function, we will use WaitGroup . Create a wg variable of the WaitGroup type, then use the Add method and set the counter to 4. Each time the copy function is executed, the Done method is called, which reduces the counter value by 1. The Wait method is called strictly before the image is encoded to ensure the generation of all four pieces of the mosaic for a solid picture.



Recall that the combine function accepts 4 channels of cut functions containing segments of photomasaics. In fact, it is not clear exactly when the segments appear in the channels. You can try to get these segments sequentially, but this is not like a competitive approach. But I would like to start processing the segment as soon as it is received using the select statement.

 var s1, s2, s3, s4 image.Image var ok1, ok2, ok3, ok4 bool for { select { case s1, ok1 = <-c1: go copy(img, s1.Bounds(), s1, image.Point{r.Min.X, r.Min.Y}) case s2, ok2 = <-c2: go copy(img, s2.Bounds(), s2, image.Point{r.Max.X / 2, r.Min.Y}) case s3, ok3 = <-c3: go copy(img, s3.Bounds(), s3, image.Point{r.Min.X, r.Max.Y / 2}) case s4, ok4 = <-c4: go copy(img, s4.Bounds(), s4, image.Point{r.Max.X / 2, r.Max.Y / 2}) } if (ok1 && ok2 && ok3 && ok4) { break } } 

This is an infinite loop that at each iteration tries to choose a case with ready data (if data came simultaneously from several channels, then Go randomly selects one case and executes it). When you receive an image.Image for the channel, we run the copy and copy gorutina function. I note that the channel takes several values. The second value (ok1, ok2, ok3 or ok4) informs us about the fact of receiving data from the channel. The endless loop is interrupted after receiving data from all four channels.



Next, remember the type of WaitGroup, which was used earlier. Remember, the combine function connects the obtained parts of photo mosaic in separate mountain fields, which may not be completed at the same time. Therefore, the Wait method of the WaitGroup type blocks the encoding of the image until all the parts are assembled together.



A screenshot with the same picture and the result of the mosaic generation:





Competitive web application photo mosaic



Your keen eye can notice the differences between the generated photo mosaics. The final mosaic is assembled from 4 parts and the algorithm does not soften rough edges. However, the performance difference is obvious - the base application generated a mosaic in 2.25 seconds, and the competitive implementation does the same thing four times faster, in 646 milliseconds.



The attentive reader could note that both web applications run only on one processor core. As Rob Pike writes in his article “ Competitiveness - not parallelism ,” this is how I took a simple algorithm and divided it into lightweight threads without a parallel call! None of the gorutin is running in parallel (after all, only 1 CPU is used), despite the fact that they run independently.



Of course, it would be cruel not to take the last step, which will show how to run all this on several cores of your processor. To do this, simply install GOMAXPROCS in runtime equal to the number of cores of your processor. Changes need to be entered in the main.go file. Remember to import the runtime package before making changes.

(Note. Trans. - not relevant, since Go 1.5 version. The fact is that up to 1.5, the default value of GOMAXPROCS was 1, as the author says. Starting from 1.5, the default GOMAXPROCS will be equal to the number of your cores)

 func main() { //      fmt.Println("Number of CPUs:", runtime.NumCPU()) runtime.GOMAXPROCS(runtime.NumCPU()) fmt.Println("Starting mosaic server ...") mux := http.NewServeMux() files := http.FileServer(http.Dir("public")) mux.Handle("/static/", http.StripPrefix("/static/", files)) mux.HandleFunc("/", upload) mux.HandleFunc("/mosaic", mosaic) server := &http.Server{ Addr: "127.0.0.1:8080", Handler: mux, } TILESDB = tilesDB() fmt.Println("Mosaic server started.") server.ListenAndServe() } 

Compiled and uploaded our cat image again:





Competitive web photo-photo application launched on 8 CPUs



As you can see, the speed has increased by 3 times: from 646 milliseconds to 216 milliseconds! And if we compare this time with our original web application that generated the mosaic in 2.25 seconds, the performance increased 10 times! This is a real comparison. We did not run our original application on 8 cores, but if we had done this, we would not have seen a performance boost, since it did not use competition.



It is also interesting to note that we used the same algorithm for single-threaded and competitive implementation of the photo mosaic generation algorithm. In fact, we did not make changes to the mosaic.go file. It is a testament.