summaryrefslogtreecommitdiff
path: root/integralimg.go
blob: f952c560bd69b7b44cf9f8c870ac55a66cf651aa (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
// Copyright 2019 Nick White.
// Use of this source code is governed by the GPLv3
// license that can be found in the LICENSE file.

// integralimg is a package for processing integral images, aka
// summed area tables. These are structures which precompute the
// sum of pixels to the left and above each pixel, which can make
// several common image processing operations much faster.
//
// integralimg.Image and integralimg.SqImage fully implement the
// image.Image and image/draw.Draw interfaces, and hence can be
// used like so:
//
//     img, _, err := image.Decode(f)
//     integral := integralimg.NewImage(b)
//     draw.Draw(integral, b, img, b.Min, draw.Src)
//
// This package also defines a Window, which is a rectangular
// section of an integral image. This has several methods to do
// useful calculations on the part of the image represented.
package integralimg

import (
	"image"
	"image/color"
	"math"
)

// Image is an integral Image
type Image [][]uint64

// SqImage is a Square integral Image.
// A squared integral image is an integral image for which the square of
// each pixel is saved; this is useful for efficiently calculating
// Standard Deviation.
type SqImage [][]uint64

func (i Image) ColorModel() color.Model { return color.Gray16Model }

func (i Image) Bounds() image.Rectangle {
	return image.Rect(0, 0, len(i[0]), len(i))
}

// at64 is used to return the raw uint64 for a given pixel. Accessing
// this separately to a (potentially lossy) conversion to a Gray16 is
// necessary for SqImage to function accurately.
func (i Image) at64(x, y int) uint64 {
	if !(image.Point{x, y}.In(i.Bounds())) {
		return 0
	}

	var prevx, prevy, prevxy uint64
	prevx, prevy, prevxy = 0, 0, 0
	if x > 0 {
		prevx = i[y][x-1]
	}
	if y > 0 {
		prevy = i[y-1][x]
	}
	if x > 0 && y > 0 {
		prevxy = i[y-1][x-1]
	}
	orig := i[y][x] + prevxy - prevx - prevy
	return orig
}

func (i Image) At(x, y int) color.Color {
	c := i.at64(x, y)
	return color.Gray16{uint16(c)}
}

func (i Image) set64(x, y int, c uint64) {
	var prevx, prevy, prevxy uint64
	prevx, prevy, prevxy = 0, 0, 0
	if x > 0 {
		prevx = i[y][x-1]
	}
	if y > 0 {
		prevy = i[y-1][x]
	}
	if x > 0 && y > 0 {
		prevxy = i[y-1][x-1]
	}
	final := c + prevx + prevy - prevxy
	i[y][x] = final
}

func (i Image) Set(x, y int, c color.Color) {
	gray := color.Gray16Model.Convert(c).(color.Gray16).Y
	i.set64(x, y, uint64(gray))
}

// NewImage returns a new integral Image with the given bounds.
func NewImage(r image.Rectangle) *Image {
	w, h := r.Dx(), r.Dy()
	var rows Image
	for i := 0; i < h; i++ {
		col := make([]uint64, w)
		rows = append(rows, col)
	}
	return &rows
}

func (i SqImage) ColorModel() color.Model { return Image(i).ColorModel() }

func (i SqImage) Bounds() image.Rectangle {
	return Image(i).Bounds()
}

func (i SqImage) At(x, y int) color.Color {
	c := Image(i).at64(x, y)
	rt := math.Sqrt(float64(c))
	return color.Gray16{uint16(rt)}
}

func (i SqImage) Set(x, y int, c color.Color) {
	gray := uint64(color.Gray16Model.Convert(c).(color.Gray16).Y)
	Image(i).set64(x, y, gray * gray)
}

// NewSqImage returns a new squared integral Image with the given bounds.
func NewSqImage(r image.Rectangle) *SqImage {
	i := NewImage(r)
	s := SqImage(*i)
	return &s
}

func lowest(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func highest(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func (i Image) topLeft(r image.Rectangle) uint64 {
	x := highest(r.Min.X, 0)
	y := highest(r.Min.Y, 0)
	return i[y][x]
}

func (i Image) topRight(r image.Rectangle) uint64 {
	x := lowest(r.Max.X, i.Bounds().Dx() - 1)
	y := highest(r.Min.Y, 0)
	return i[y][x]
}

func (i Image) bottomLeft(r image.Rectangle) uint64 {
	x := highest(r.Min.X, 0)
	y := lowest(r.Max.Y, i.Bounds().Dy() - 1)
	return i[y][x]
}

func (i Image) bottomRight(r image.Rectangle) uint64 {
	x := lowest(r.Max.X, i.Bounds().Dx() - 1)
	y := lowest(r.Max.Y, i.Bounds().Dy() - 1)
	return i[y][x]
}

// Sum returns the sum of all pixels in a rectangle
func (i Image) Sum(r image.Rectangle) uint64 {
	return i.bottomRight(r) + i.topLeft(r) - i.topRight(r) - i.bottomLeft(r)
}

// Mean returns the average value of pixels in a rectangle
func (i Image) Mean(r image.Rectangle) float64 {
	in := r.Intersect(i.Bounds())
	return float64(i.Sum(r)) / float64(in.Dx() * in.Dy())
}

// Sum returns the sum of all pixels in a rectangle
func (i SqImage) Sum(r image.Rectangle) uint64 {
	return Image(i).Sum(r)
}

// Mean returns the average value of pixels in a rectangle
func (i SqImage) Mean(r image.Rectangle) float64 {
	return Image(i).Mean(r)
}

// Proportion returns the proportion of pixels which are not white
func (i Image) ProportionNotWhite(r image.Rectangle) float64 {
	in := r.Intersect(i.Bounds())
	area := in.Dx() * in.Dy()
	// 1 << 16 - 1 as we're using Gray16, so 1 << 16 - 1 = white
	sum := float64(i.Sum(r)) / float64(1 << 16 - 1)
	return 1 - float64(area) / float64(sum)
}

// MeanStdDev calculates the mean and standard deviation of a
// section of an image, using the corresponding regular and square
// integral images.
func MeanStdDev(i Image, sq SqImage, r image.Rectangle) (float64, float64) {
	imean := i.Mean(r)
	smean := sq.Mean(r)

	variance := smean - (imean * imean)

	return imean, math.Sqrt(variance)
}

// Window is a section of an Integral Image
type Window struct {
	topleft uint64
	topright uint64
	bottomleft uint64
	bottomright uint64
	width int
	height int
}

// GetWindow gets the values of the corners of a square part of an
// Integral Image, plus the dimensions of the part, which can
// be used to quickly calculate the mean of the area
func (i Image) GetWindow(x, y, size int) Window {
	step := size / 2

	minx, miny := 0, 0
	maxy := i.Bounds().Dy() - 1
	maxx := i.Bounds().Dx() - 1

	if y > (step+1) {
		miny = y - step - 1
	}
	if x > (step+1) {
		minx = x - step - 1
	}

	if maxy > (y + step) {
		maxy = y + step
	}
	if maxx > (x + step) {
		maxx = x + step
	}

	return Window { i[miny][minx], i[miny][maxx], i[maxy][minx], i[maxy][maxx], maxx-minx, maxy-miny}
}

func (i SqImage) GetWindow(x, y, size int) Window {
	return Image(i).GetWindow(x, y, size)
}

// GetVerticalWindow gets the values of the corners of a vertical
// slice of an Integral Image, starting at x
func (i Image) GetVerticalWindow(x, width int) Window {
	maxy := i.Bounds().Dy() - 1
	xbound := i.Bounds().Dx() - 1
	maxx := x + width
	if maxx > xbound {
		maxx = xbound
	}

	return Window { i[0][x], i[0][maxx], i[maxy][x], i[maxy][maxx], width, maxy }
}

func (i SqImage) GetVerticalWindow(x, width int) Window {
	return Image(i).GetVerticalWindow(x, width)
}

// Sum returns the sum of all pixels in a Window
func (w Window) Sum() uint64 {
	return w.bottomright + w.topleft - w.topright - w.bottomleft
}

// Size returns the total size of a Window
func (w Window) Size() int {
	return w.width * w.height
}

// Mean returns the average value of pixels in a Window
func (w Window) Mean() float64 {
	return float64(w.Sum()) / float64(w.Size())
}

// Proportion returns the proportion of pixels which are on
func (w Window) Proportion() float64 {
	area := w.width * w.height
	// 1 << 16 - 1 as we're using Gray16, so for a binarised
	// image then 1 << 16 - 1 = on
	sum := float64(w.Sum()) / float64(1 << 16 - 1)
	return float64(area) / float64(sum) - 1
}

// MeanStdDevWindow calculates the mean and standard deviation of
// a section on an Integral Image, using the corresponding Square
// Integral Image.
func MeanStdDevWindow(i Image, sq SqImage, x, y, size int) (float64, float64) {
	imean := i.GetWindow(x, y, size).Mean()
	smean := sq.GetWindow(x, y, size).Mean()

	variance := smean - (imean * imean)

	return imean, math.Sqrt(variance)
}