1package hints
2
3import (
4 "image"
5 "math"
6 "sort"
7
8 "github.com/bnema/neferwl/internal/ports"
9)
10
11// underlineCandidate is a word with a thin line under it.
12type underlineCandidate struct {
13 word int
14 row int // the line's row
15 from, to int // x extent of the continuous line through the word
16}
17
18// markUnderlined sets Underlined, UnderL and UnderR on the words of a band
19// that have a thin line under them. words are in the coordinates of g.
20// Lines that run on far beyond the word (rules, table borders, input boxes)
21// do not count, unless the extension is made of underlined words too.
22func markUnderlined(src *image.Gray, words []OCRWord) {
23 // Words are relative to the band's own origin, whatever the image is a
24 // view of.
25 b := src.Bounds()
26 g := &image.Gray{Pix: src.Pix[src.PixOffset(b.Min.X, b.Min.Y):], Stride: src.Stride, Rect: image.Rect(0, 0, b.Dx(), b.Dy())}
27 var cands []underlineCandidate
28 for i, w := range words {
29 // A single glyph, or a box narrower than tall, has a flat bottom
30 // stroke (8, L, 2) that is not an underline.
31 if len([]rune(w.Text)) < 2 || w.Rect.Dx() < w.Rect.Dy() {
32 continue
33 }
34 if c, ok := underlineOf(g, w.Rect); ok {
35 c.word = i
36 cands = append(cands, c)
37 }
38 }
39 for _, c := range cands {
40 w := words[c.word]
41 h := w.Rect.Dy()
42 if (w.Rect.Min.X-c.from > h && !covered(words, cands, c, -1)) ||
43 (c.to-w.Rect.Max.X > h && !covered(words, cands, c, 1)) {
44 continue
45 }
46 words[c.word].Underlined, words[c.word].UnderL, words[c.word].UnderR = true, c.from, c.to
47 }
48}
49
50// covered reports whether the line of c, on the given side of its word, is
51// explained by underlined words on the same line up to within a glyph of its
52// end.
53func covered(words []OCRWord, cands []underlineCandidate, c underlineCandidate, dir int) bool {
54 w := words[c.word].Rect
55 h := w.Dy()
56 cur := w.Min.X
57 if dir > 0 {
58 cur = w.Max.X
59 }
60 for {
61 if (dir < 0 && cur-c.from <= h) || (dir > 0 && c.to-cur <= h) {
62 return true
63 }
64 next := -1
65 for _, o := range cands {
66 r := words[o.word].Rect
67 if abs(r.Max.Y-w.Max.Y) > max(3, h/3) {
68 continue
69 }
70 var gap, reach int
71 if dir < 0 {
72 gap, reach = cur-r.Max.X, r.Min.X
73 } else {
74 gap, reach = r.Min.X-cur, r.Max.X
75 }
76 if gap < -2 || gap > h {
77 continue
78 }
79 if next < 0 || (dir < 0 && reach < next) || (dir > 0 && reach > next) {
80 next = reach
81 }
82 }
83 if next < 0 || (dir < 0 && next >= cur) || (dir > 0 && next <= cur) {
84 return false
85 }
86 cur = next
87 }
88}
89
90// underlineOf looks for an underline under the word box r in g.
91func underlineOf(g *image.Gray, r image.Rectangle) (underlineCandidate, bool) {
92 b := g.Bounds()
93 box := r.Intersect(b)
94 h := r.Dy()
95 if box.Dx() < 4 || h < 4 {
96 return underlineCandidate{}, false
97 }
98 bg, ink := contrastOf(g, box)
99 thr := min(40, max(20, ink/2))
100 if ink < thr+10 {
101 return underlineCandidate{}, false
102 }
103 top := max(b.Min.Y, r.Max.Y-(h*15+99)/100)
104 bottom := min(b.Max.Y, r.Max.Y+(h*35+99)/100+1)
105 maxThick := max(2, h/6)
106 rowOK := func(y int) bool {
107 row := g.Pix[(y-g.Rect.Min.Y)*g.Stride:]
108 n := 0
109 for x := box.Min.X; x < box.Max.X; x++ {
110 if abs(int(row[x-g.Rect.Min.X])-bg) >= thr {
111 n++
112 }
113 }
114 return n*100 >= box.Dx()*85
115 }
116 thick, first := 0, 0
117 for y := top; y <= bottom; y++ {
118 if y < bottom && rowOK(y) {
119 if thick == 0 {
120 first = y
121 }
122 thick++
123 continue
124 }
125 if thick > 0 {
126 if thick > maxThick {
127 return underlineCandidate{}, false // a block, not a line
128 }
129 row := first + thick/2
130 from, to := box.Min.X, box.Max.X
131 line := g.Pix[(row-g.Rect.Min.Y)*g.Stride:]
132 on := func(x int) bool { return abs(int(line[x-g.Rect.Min.X])-bg) >= thr }
133 for from > b.Min.X && on(from-1) {
134 from--
135 }
136 for to < b.Max.X && on(to) {
137 to++
138 }
139 return underlineCandidate{row: row, from: from, to: to}, true
140 }
141 }
142 return underlineCandidate{}, false
143}
144
145// contrastOf returns the background level of box (the most common level,
146// found in bins of 16 so antialiasing does not split it, then refined to the
147// mean of that bin) and the contrast of its ink (the deviation reached by
148// the strongest 3% of pixels).
149func contrastOf(g *image.Gray, box image.Rectangle) (bg, ink int) {
150 var hist [256]int
151 for y := box.Min.Y; y < box.Max.Y; y++ {
152 for _, v := range g.Pix[(y-g.Rect.Min.Y)*g.Stride+box.Min.X-g.Rect.Min.X:][:box.Dx()] {
153 hist[v]++
154 }
155 }
156 total := box.Dx() * box.Dy()
157 var bins [16]int
158 for v, c := range hist {
159 bins[v>>4] += c
160 }
161 best := 0
162 for i, c := range bins {
163 if c > bins[best] {
164 best = i
165 }
166 }
167 sum, n := 0, 0
168 for v := best << 4; v < (best+1)<<4; v++ {
169 sum += v * hist[v]
170 n += hist[v]
171 }
172 bg = sum / max(n, 1)
173 var dev [256]int
174 for v, c := range hist {
175 dev[abs(v-bg)] += c
176 }
177 n = 0
178 for d := 255; d >= 0; d-- {
179 n += dev[d]
180 if n*100 >= total*3 {
181 return bg, d
182 }
183 }
184 return bg, 0
185}
186
187// underlinedLinks returns the targets for underlined words, joining the
188// words of one continuous underline. A group that overlaps a URL target (in
189// pixels) is left to it. Coordinates are scaled to logical.
190func underlinedLinks(words []OCRWord, urls []image.Rectangle, scale float64) []ports.HintTarget {
191 var us []OCRWord
192 for _, w := range words {
193 if w.Underlined {
194 us = append(us, w)
195 }
196 }
197 sort.Slice(us, func(i, j int) bool { return us[i].Rect.Min.X < us[j].Rect.Min.X })
198 used := make([]bool, len(us))
199 var out []ports.HintTarget
200 for i := range us {
201 if used[i] {
202 continue
203 }
204 used[i] = true
205 rect, last := us[i].Rect, us[i]
206 chars, width := len(last.Text), last.Rect.Dx()
207 for {
208 next := -1
209 for j := range us {
210 c := us[j]
211 if used[j] || c.Rect.Min.X < rect.Max.X-2 || abs(c.Rect.Max.Y-last.Rect.Max.Y) > max(3, rect.Dy()/3) {
212 continue
213 }
214 avg := float64(width+c.Rect.Dx()) / float64(max(1, chars+len(c.Text)))
215 gap := c.Rect.Min.X - rect.Max.X
216 if float64(gap) > 1.2*avg || c.Rect.Min.X > last.UnderR+2 {
217 continue
218 }
219 if next < 0 || c.Rect.Min.X < us[next].Rect.Min.X {
220 next = j
221 }
222 }
223 if next < 0 {
224 break
225 }
226 used[next] = true
227 last = us[next]
228 rect = rect.Union(last.Rect)
229 chars += len(last.Text)
230 width += last.Rect.Dx()
231 }
232 dup := false
233 for _, u := range urls {
234 if overlap(rect, u) > .5 {
235 dup = true
236 }
237 }
238 if dup {
239 continue
240 }
241 x, y := int(math.Floor(float64(rect.Min.X)/scale)), int(math.Floor(float64(rect.Min.Y)/scale))
242 right, bottom := int(math.Ceil(float64(rect.Max.X)/scale)), int(math.Ceil(float64(rect.Max.Y)/scale))
243 out = append(out, ports.HintTarget{Kind: ports.HintLink, Rect: ports.Rect{X: x, Y: y, W: right - x, H: bottom - y}})
244 }
245 return out
246}