-
Notifications
You must be signed in to change notification settings - Fork 0
/
distanceselector.go
155 lines (138 loc) · 4.37 KB
/
distanceselector.go
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
// Copyright 2019 Fabian Wenzelmann
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package gomosaic
import (
"image"
"math"
)
// intManhattanDist returns the manhattan distance of two two-dimensional points
// (x1, y1) and (x2, y2).
func intManhattanDist(p1, p2 image.Point) int {
return IntAbs(p1.X-p2.X) + IntAbs(p1.Y-p2.Y)
}
func getClosestManhattan(p image.Point, comparePoints []image.Point) int {
currentMin := MaxInt
for _, cmp := range comparePoints {
dist := intManhattanDist(p, cmp)
if dist < currentMin {
currentMin = dist
}
}
return currentMin
}
type assignedImageMap map[ImageID][]image.Point
func newAssignedImageMap(storage ImageStorage) assignedImageMap {
result := make(assignedImageMap, int(storage.NumImages()))
return result
}
func (m assignedImageMap) assignImage(img ImageID, tile image.Point) {
if _, hasImage := m[img]; !hasImage {
m[img] = make([]image.Point, 0, 1)
}
m[img] = append(m[img], tile)
}
func (m assignedImageMap) getAssigned(img ImageID) []image.Point {
if res, has := m[img]; has {
return res
}
return nil
}
type DistanceHeapSelector struct {
Metric ImageMetric
K int
NumRoutines int
}
func NewDistanceHeapSelector(metric ImageMetric, k, numRoutines int) *DistanceHeapSelector {
if numRoutines <= 0 {
numRoutines = 1
}
return &DistanceHeapSelector{
Metric: metric,
K: k,
NumRoutines: numRoutines,
}
}
func (selector *DistanceHeapSelector) Init(storage ImageStorage) error {
return selector.Metric.InitStorage(storage)
}
func (selector *DistanceHeapSelector) SelectImages(storage ImageStorage,
query image.Image, dist TileDivision, progress ProgressFunc) ([][]ImageID, error) {
if initErr := selector.Metric.InitTiles(storage, query, dist); initErr != nil {
return nil, initErr
}
// computes heaps
heaps, heapsErr := ComputeHeaps(storage, selector.Metric, query, dist, selector.K,
selector.NumRoutines, progress)
if heapsErr != nil {
return nil, heapsErr
}
// first create a new mapping from image --> tiles the image was used in
currentAssignment := newAssignedImageMap(storage)
result := make([][]ImageID, len(dist))
// initialize result slices
for i, inner := range dist {
size := len(inner)
result[i] = make([]ImageID, size)
for j := 0; j < size; j++ {
result[i][j] = NoImageID
}
}
for i, inner := range dist {
size := len(inner)
for j := 0; j < size; j++ {
// get rectangle for this tile
rect := inner[j]
currentPoint := rect.Min
// now iterate over all images in the heap for this position
// select the image with the maximum distance to the tile
// (when was the image assigned the last time?)
// for this we compute for each candidate the closes manhattan distance
// (when was the image last used close to the current point?)
// the assumption is that all images in the heap are considered a good candidate
// the one that has the highest manhattan distance is considered best (far away)
// so for each image we select the minimal manhattan distance to all positions
// this image was used
// then we select the one with the highest value
// if two images have the same manhattan distance we furthermore take the
// metric into account
heap := heaps[i][j]
view := heap.GetView()
maxDist := MinInt
bestImage := NoImageID
bestMetric := math.MaxFloat64
for _, entry := range view {
img := entry.Image
metricValue := entry.Value
dist := getClosestManhattan(currentPoint, currentAssignment.getAssigned(img))
switch {
case dist == maxDist:
if metricValue < bestMetric {
bestImage = img
bestMetric = metricValue
}
case dist > maxDist:
maxDist = dist
bestImage = img
bestMetric = metricValue
}
}
// assign image
if bestImage != NoImageID {
result[i][j] = bestImage
currentAssignment.assignImage(bestImage, currentPoint)
}
}
}
return result, nil
}