Line data Source code
1 :
2 : /* Copyright (c) 2009, Maxim Makhinya
3 : * 2010-2013, Stefan Eilemann <eile@eyescale.ch>
4 : *
5 : * This library is free software; you can redistribute it and/or modify it under
6 : * the terms of the GNU Lesser General Public License version 2.1 as published
7 : * by the Free Software Foundation.
8 : *
9 : * This library is distributed in the hope that it will be useful, but WITHOUT
10 : * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11 : * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
12 : * details.
13 : *
14 : * You should have received a copy of the GNU Lesser General Public License
15 : * along with this library; if not, write to the Free Software Foundation, Inc.,
16 : * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
17 : */
18 :
19 : #include "roiEmptySpaceFinder.h"
20 :
21 : #include <eq/fabric/pixelViewport.h>
22 :
23 : namespace eq
24 : {
25 0 : void ROIEmptySpaceFinder::_resize(const int32_t w, const int32_t h)
26 : {
27 0 : _w = w;
28 0 : _h = h;
29 :
30 0 : _mask = 0;
31 :
32 0 : if (static_cast<int32_t>(_data.size()) < w * h)
33 0 : _data.resize(w * h);
34 :
35 0 : setLimits((w - 1) * (h - 1), 1.0);
36 0 : }
37 :
38 0 : void ROIEmptySpaceFinder::update(const uint8_t* mask, const int32_t w,
39 : const int32_t h)
40 : {
41 0 : _resize(w, h);
42 :
43 0 : _mask = mask;
44 0 : const uint8_t* s = mask + _w * (_h - 1);
45 0 : uint16_t* d = &_data[_w * (_h - 1)];
46 :
47 : // First element
48 0 : d[_w - 1] = s[_w - 1] > 0 ? 1 : 0;
49 :
50 : // First raw
51 0 : for (int32_t x = _w - 2; x >= 0; x--)
52 0 : d[x] = d[x + 1] + (s[x] > 0 ? 1 : 0);
53 :
54 : // All other raws
55 0 : for (int32_t y = 1; y < _h; y++)
56 : {
57 0 : const uint16_t* dp = d; // previous calculated raw
58 0 : s -= _w;
59 0 : d -= _w;
60 0 : uint16_t rawSum = 0;
61 0 : for (int32_t x = _w - 1; x >= 0; x--)
62 : {
63 0 : rawSum += s[x] > 0 ? 1 : 0;
64 0 : d[x] = dp[x] + rawSum;
65 : }
66 : }
67 0 : }
68 :
69 0 : inline uint16_t ROIEmptySpaceFinder::_getArea(const int32_t x, const int32_t y,
70 : const int32_t w,
71 : const int32_t h) const
72 : {
73 0 : return _getArea(w, h, &_data[0] + y * _w + x);
74 : }
75 :
76 0 : inline uint16_t ROIEmptySpaceFinder::_getArea(const int32_t w, const int32_t h,
77 : const uint16_t* data) const
78 : {
79 0 : const uint16_t* data_ = data + h * _w;
80 0 : return *data - data[w] - *data_ + data_[w];
81 : }
82 :
83 0 : bool ROIEmptySpaceFinder::_updateMaximalEmptyRegion(
84 : const int32_t x, const int32_t y, const int32_t w, const int32_t h,
85 : PixelViewport& pvp, const uint16_t* data) const
86 : {
87 0 : uint16_t maxArea = pvp.w * pvp.h;
88 0 : bool updated = false;
89 0 : int32_t maxW = 0;
90 0 : int32_t maxH = 0;
91 :
92 : // find biggest diagonal
93 0 : int32_t cwh = 2;
94 0 : while (cwh <= w && cwh <= h && _getArea(cwh, cwh, data) == 0)
95 0 : cwh++;
96 :
97 0 : cwh--;
98 :
99 0 : if (cwh * cwh > maxArea)
100 : {
101 0 : maxArea = cwh * cwh;
102 0 : maxW = cwh;
103 0 : maxH = cwh;
104 0 : updated = true;
105 : }
106 :
107 : // check parallelepipids
108 0 : if (cwh * w > maxArea)
109 : {
110 0 : int32_t ch = cwh;
111 0 : for (int32_t cw = cwh + 1; cw <= w; cw++)
112 : {
113 0 : while (_getArea(cw, ch, data) != 0)
114 : {
115 0 : ch--;
116 0 : if (ch == 0)
117 : {
118 0 : cw = w + 1;
119 0 : break;
120 : }
121 : }
122 0 : if (cw * ch > maxArea)
123 : {
124 0 : maxArea = cw * ch;
125 0 : maxW = cw;
126 0 : maxH = ch;
127 0 : updated = true;
128 : }
129 : }
130 : }
131 :
132 0 : if (cwh * h > maxArea)
133 : {
134 0 : int32_t cw = cwh;
135 0 : for (int32_t ch = cwh + 1; ch <= h; ch++)
136 : {
137 0 : while (_getArea(cw, ch, data) != 0)
138 : {
139 0 : cw--;
140 0 : if (cw == 0)
141 : {
142 0 : ch = h + 1;
143 0 : break;
144 : }
145 : }
146 0 : if (cw * ch > maxArea)
147 : {
148 0 : maxArea = cw * ch;
149 0 : maxW = cw;
150 0 : maxH = ch;
151 0 : updated = true;
152 : }
153 : }
154 : }
155 :
156 0 : if (updated)
157 0 : pvp = PixelViewport(x, y, maxW, maxH);
158 :
159 0 : return updated;
160 : }
161 :
162 0 : PixelViewport ROIEmptySpaceFinder::getLargestEmptyArea(
163 : const PixelViewport& pvp) const
164 : {
165 0 : LBASSERT(pvp.x >= 0 && pvp.w > 0 && pvp.y >= 0 && pvp.h > 0 &&
166 : pvp.x + pvp.w < _w && pvp.y + pvp.h < _h);
167 :
168 0 : LBASSERT(_mask);
169 :
170 0 : PixelViewport res(pvp.x, pvp.y, 0, 0);
171 :
172 0 : uint16_t maxArea = _getArea(pvp.x, pvp.y, pvp.w, pvp.h);
173 0 : const uint16_t minRel = static_cast<uint16_t>(pvp.w * pvp.h * _limRel);
174 :
175 : // totally empty
176 0 : if (maxArea == 0)
177 0 : return pvp;
178 :
179 : // totally full
180 0 : if (maxArea == pvp.w * pvp.h)
181 0 : return res;
182 :
183 : // over limit
184 0 : if (maxArea < _limAbs || maxArea < minRel)
185 0 : return res;
186 :
187 : // search for biggest empty pvp
188 0 : const uint16_t* data = &_data[0] + pvp.y * _w;
189 0 : const uint8_t* m = _mask + pvp.y * _w;
190 :
191 0 : maxArea = 0;
192 :
193 0 : for (int y = pvp.y, h = pvp.h; h > 0; y++, h--)
194 : {
195 : // skeep if found area bigger than the rest of image
196 0 : if (h * pvp.w - _getArea(pvp.x, y, pvp.w, h) <= maxArea)
197 0 : break;
198 :
199 0 : for (int x = pvp.x, w = pvp.w; w > 0; x++, w--)
200 : {
201 : // skeep non empty blocks
202 0 : if (m[x] != 0)
203 0 : continue;
204 :
205 : // skeep if found area bigger than the rest of image
206 0 : if (w * h - _getArea(w, h, data + x) <= maxArea)
207 : {
208 0 : w = 0;
209 0 : continue;
210 : }
211 :
212 0 : if (_updateMaximalEmptyRegion(x, y, w, h, res, data + x))
213 0 : maxArea = res.w * res.h;
214 : }
215 0 : m += _w;
216 0 : data += _w;
217 : }
218 :
219 0 : const uint16_t curArea = res.w * res.h;
220 0 : if (curArea < _limAbs || curArea < minRel)
221 0 : return PixelViewport(pvp.x, pvp.y, 0, 0);
222 :
223 0 : return res;
224 : }
225 30 : }
|
