Switch binarization to Sauvola algorithm

2 files changed, 96 insertions, 3 deletions

diff --git a/binarize/binarize.go b/binarize/binarize.go
index f95ee22..fa8a30f 100644
--- a/binarize/binarize.go
+++ b/binarize/binarize.go
@@ -7,14 +7,15 @@ import (
 	"os"
 
 	"github.com/Ernyoke/Imger/imgio"
-	"github.com/Ernyoke/Imger/threshold"
 )
 
 func main() {
 	flag.Usage = func() {
-		fmt.Fprintf(os.Stderr, "Usage: binarize inimg outimg\n")
+		fmt.Fprintf(os.Stderr, "Usage: binarize [-w num] [-k num] inimg outimg\n")
 		flag.PrintDefaults()
 	}
+	wsize := flag.Int("w", 31, "Window size for sauvola algorithm")
+        ksize := flag.Float64("k", 0.5, "K for sauvola algorithm")
 	flag.Parse()
 	if flag.NArg() < 2 {
 		flag.Usage()
@@ -26,7 +27,8 @@ func main() {
 		log.Fatalf("Could not read image %s\n", flag.Arg(0))
 	}
 
-	thresh, err := threshold.OtsuThreshold(img, threshold.ThreshBinary)
+	// TODO: should be able to estimate an appropriate window size based on resolution
+	thresh := Sauvola(img, *ksize, *wsize)
 	if err != nil {
 		log.Fatal("Error binarising image\n")
 	}
diff --git a/binarize/sauvola.go b/binarize/sauvola.go
new file mode 100644
index 0000000..f1d0512
--- /dev/null
+++ b/binarize/sauvola.go
@@ -0,0 +1,91 @@
+package main
+
+import (
+	"image"
+	"image/color"
+	"math"
+)
+
+func mean(i []int) float64 {
+	sum := 0
+	for _, n := range i {
+		sum += n
+	}
+	return float64(sum) / float64(len(i))
+}
+
+// TODO: is there a prettier way of doing this than float64() all over the place?
+func stddev(i []int) float64 {
+	m := mean(i)
+
+	var sum float64
+	for _, n := range i {
+		sum += (float64(n) - m) * (float64(n) - m)
+	}
+	variance := float64(sum) / float64(len(i) - 1)
+	return math.Sqrt(variance)
+}
+
+func meanstddev(i []int) (float64, float64) {
+	m := mean(i)
+
+	var sum float64
+	for _, n := range i {
+		sum += (float64(n) - m) * (float64(n) - m)
+	}
+	variance := float64(sum) / float64(len(i) - 1)
+	return m, math.Sqrt(variance)
+}
+
+// gets the pixel values surrounding a point in the image
+func surrounding(img *image.Gray, x int, y int, size int) []int {
+	b := img.Bounds()
+
+	miny := y - size/2
+	if miny < b.Min.Y {
+		miny = b.Min.Y
+	}
+	minx := x - size/2
+	if minx < b.Min.X {
+		minx = b.Min.X
+	}
+	maxy := y + size/2
+	if maxy > b.Max.Y {
+		maxy = b.Max.Y
+	}
+	maxx := x + size/2
+	if maxx > b.Max.X {
+		maxx = b.Max.X
+	}
+
+	var s []int
+	for yi := miny; yi < maxy; yi++ {
+		for xi := minx; xi < maxx; xi++ {
+			s = append(s, int(img.GrayAt(xi, yi).Y))
+		}
+	}
+	return s
+}
+
+// TODO: parallelize
+// TODO: switch to using integral images to make faster; see paper
+//       "Efficient Implementation of Local Adaptive Thresholding Techniques Using Integral Images"
+func Sauvola(img *image.Gray, ksize float64, windowsize int) *image.Gray {
+	b := img.Bounds()
+	new := image.NewGray(b)
+
+	for y := b.Min.Y; y < b.Max.Y; y++ {
+		for x := b.Min.X; x < b.Max.X; x++ {
+			window := surrounding(img, x, y, windowsize)
+			m, dev := meanstddev(window)
+			threshold := m * (1 + ksize * ((dev / 128) - 1))
+			if img.GrayAt(x, y).Y < uint8(threshold) {
+				new.SetGray(x, y, color.Gray{0})
+			} else {
+				new.SetGray(x, y, color.Gray{255})
+			}
+		}
+	}
+
+	return new
+}