ncc.go

package lookup

import (
	"fmt"
	"math"
)

// GPoint represents a match of a template inside an image.
type GPoint struct {
	X, Y int
	G    float64
}

func lookupAll(imgBin *imageBinary, x1, y1, x2, y2 int, templateBin *imageBinary, m float64) ([]GPoint, error) {
	var list []GPoint

	templateWidth := templateBin.width
	templateHeight := templateBin.height
	for x := x1; x <= x2-templateWidth+1; x++ {
		for y := y1; y <= y2-templateHeight+1; y++ {
			g, err := lookup(imgBin, templateBin, x, y, m)
			if err != nil {
				return nil, err
			}
			if g != nil {
				list = append(list, *g)
			}
		}
	}
	return list, nil
}

//  Normalized Cross Correlation algorithm
//  1) mean && stddev
//  2) image1(x,y) - mean1 && image2(x,y) - mean2
//  3) [3] = (image1(x,y) - mean)(x,y) * (image2(x,y) - mean)(x,y)
//  4) [4] = mean([3])
//  5) [4] / (stddev1 * stddev2)
//
// See http://www.fmwconcepts.com/imagemagick/similar/index.php
func lookup(img *imageBinary, template *imageBinary, x int, y int, m float64) (*GPoint, error) {
	ci := img.channels
	ct := template.channels

	ii := min(len(ci), len(ct))
	g := math.MaxFloat64

	for i := 0; i < ii; i++ {
		cct := ct[i]
		cci := ci[i]
		if cct.channelType != cci.channelType {
			return nil, fmt.Errorf("incompatible channels %d <> %d", cct.channelType, cci.channelType)
		}
		gg := gamma(cci, cct, x, y)
		if gg < m {
			return nil, nil
		}
		g = math.Min(g, gg)
	}
	return &GPoint{X: x, Y: y, G: g}, nil
}

func gamma(img *imageBinaryChannel, template *imageBinaryChannel, xx int, yy int) float64 {
	d := denominator(img, template, xx, yy)
	if d == 0 {
		return -1
	}

	n := numerator(img, template, xx, yy)
	return n / d
}

func denominator(img *imageBinaryChannel, template *imageBinaryChannel, xx int, yy int) float64 {
	di := img.dev2nRect(xx, yy, xx+template.width-1, yy+template.height-1)
	dt := template.dev2n()
	return math.Sqrt(di * dt)
}

func numerator(img *imageBinaryChannel, template *imageBinaryChannel, offsetX int, offsetY int) float64 {
	imgWidth := img.width
	imgArray := img.zeroMeanImage
	templateWidth := template.width
	templateHeight := template.height
	templateArray := template.zeroMeanImage
	var sum float64
	for x := 0; x < templateWidth; x++ {
		for y := 0; y < templateHeight; y++ {
			value := imgArray[(offsetY+y)*imgWidth+offsetX+x] * templateArray[y*templateWidth+x]
			sum += value
		}
	}
	return sum
}