image pattern matching, MAD

image-pattern-matching.go

package main

import (
	"image/png"
	"os"
	"fmt"
	"time"
	"net/http"
	"log"
	"io"
	"encoding/base64"
	"strings"
)

type Img struct {
	w      int
	h      int
	colors [][]Color
}

type Color struct {
	r uint32
	g uint32
	b uint32
}

func (c *Color) same(other *Color) bool {
	return c.r == other.r && c.g == other.g && c.b == other.b
}

type Dot struct {
	row int
	col int
}

func loadByFileName(name string) (Img) {
	infile, err := os.Open(name)
	if err != nil {
		panic("can't open " + name)
	}
	defer infile.Close()

	src, err := png.Decode(infile)
	if err != nil {
		panic("can't decode " + name)
	}

	bounds := src.Bounds()
	w, h := bounds.Max.X, bounds.Max.Y

	colors := make([][]Color, h)
	for y := 0; y < h; y++ {
		cols := make([]Color, w)
		for x := 0; x < w; x++ {
			r, g, b, _ := src.At(x, y).RGBA()
			cols[x] = Color{r, g, b}
		}
		colors[y] = cols
	}
	return Img{w, h, colors}
}

func loadByFileData(data string) (Img) {
	encoder := base64.NewDecoder(base64.StdEncoding, strings.NewReader(data))

	src, err := png.Decode(encoder)
	if err != nil {
		panic("can't decode from base64")
	}

	bounds := src.Bounds()
	w, h := bounds.Max.X, bounds.Max.Y

	colors := make([][]Color, h)
	for y := 0; y < h; y++ {
		cols := make([]Color, w)
		for x := 0; x < w; x++ {
			r, g, b, _ := src.At(x, y).RGBA()
			cols[x] = Color{r, g, b}
		}
		colors[y] = cols
	}
	return Img{w, h, colors}
}

func dotIsOk(big *Img, small *Img, row int, col int) (bool) {
	for y := 0; y < small.h; y++ {
		for x := 0; x < small.w; x++ {
			if ! small.colors[y][x].same(&big.colors[row+y][col+x]) {
				return false
			}
		}
	}
	return true
}

func comparator(big *Img, small *Img, row int, dots chan []Dot) {
	var found []Dot
	for col := 0; col < big.w-small.w; col++ {
		if dotIsOk(big, small, row, col) {
			found = append(found, Dot{row, col})
		}
	}
	dots <- found
}

func main() {
	http.HandleFunc("/", findHandler)

	s := &http.Server{
		Addr:           ":8080",
		ReadTimeout:    5 * time.Second,
		WriteTimeout:   5 * time.Second,
		MaxHeaderBytes: 2 * 1024 * 1024,
	}
	log.Fatal(s.ListenAndServe())
}

func findHandler(w http.ResponseWriter, req *http.Request) {
	fmt.Println("")

	start := time.Now()

	big := loadByFileName("./big.png")
	// small := loadByFileName("./small.png")
	// small := loadByFileData("iVBORw0KGgoAAAANSUhEUgAAACQAAAAMCAIAAACFnYiUAAAACXBIWXMAAAsTAAALEwEAmpwYAAABQElEQVQ4jbWUv0rDUBSHf+cmpaUJNa1D2yESWhAU/4DOncU3cPEFBBcXn0LfQHwBdx/ASbuog9JiixUVIhaSSmwlzTkOFYWSSa/f9Dtw4OPcc+8lz/OgiVKRViwxCeEAzTClwdRmqhqHC/EkX7XQDNU/yuq2AOj6OPVVFKX36JBZam+J5+wEglIemzXp9uRmqKplte3xosX4kLNHOuopPZPF38mkzCQU1M4yu8z+ANkZ1agLxmw4jvNnlVw8IcobazY37+TgVl1HtOrSRiHxX2T/0uiK2ShyjiVljb/DAACYRJOykAGAh5AAvA4REJVtfbIp4gQAKrYAyGXFEQne9d3GKc772HLJrcouSXGWAXRCpW2yhAFg/HWKkD4fd4yA1HpFahluPePkXpHGHySFHM3ngVjab4DGR53OSNqjn+oTQvdwE5vsgosAAAAASUVORK5CYII=")
	fmt.Println("[", req.URL.Query().Get("small"), "]")
	small := loadByFileData(req.URL.Query().Get("small"))

	load := time.Now()
	fmt.Println("image load time:", load.Sub(start))
	io.WriteString(w, "image load time: "+load.Sub(start).String()+"\n")

	dots := make(chan []Dot)
	done := make(chan bool)
	processes := 0

	var found []Dot

	go func() {
	forSelect:
		for {
			select {
			case processDots := <-dots:
				for _, dot := range processDots {
					found = append(found, dot)
				}
				processes--
				if processes == 0 {
					break forSelect
				}
			case <-time.After(2 * time.Second):
				fmt.Println("timeout")
				break forSelect
			}
		}

		for _, dot := range found {
			fmt.Println("found!", dot.row, dot.col)
		}

		done <- true
	}()

	for row := 0; row < big.h-small.h; row++ {
		processes++
		go comparator(&big, &small, row, dots)
	}

	<-done

	end := time.Now()

	fmt.Println("search time:", end.Sub(load))
	io.WriteString(w, "search time: "+end.Sub(load).String()+"\n")

	fmt.Println("full time:", end.Sub(start))
	io.WriteString(w, "full time: "+end.Sub(start).String()+"\n")
}