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 :
26 0 : void ROIEmptySpaceFinder::_resize( const int32_t w, const int32_t h )
27 : {
28 0 : _w = w;
29 0 : _h = h;
30 :
31 0 : _mask = 0;
32 :
33 0 : if( static_cast<int32_t>(_data.size()) < w * h )
34 0 : _data.resize( w * h );
35 :
36 0 : setLimits( (w-1)*(h-1), 1.0 );
37 0 : }
38 :
39 :
40 0 : void ROIEmptySpaceFinder::update( const uint8_t* mask,
41 : const int32_t w,
42 : const int32_t h )
43 : {
44 0 : _resize( w, h );
45 :
46 0 : _mask = mask;
47 0 : const uint8_t* s = mask + _w*(_h-1);
48 0 : uint16_t* d = &_data[_w*(_h-1)];
49 :
50 : // First element
51 0 : d[_w-1] = s[_w-1] > 0 ? 1 : 0;
52 :
53 : // First raw
54 0 : for( int32_t x = _w-2; x >= 0; x-- )
55 0 : d[x] = d[x+1] + ( s[x] > 0 ? 1 : 0 );
56 :
57 : // All other raws
58 0 : for( int32_t y = 1; y < _h; y++ )
59 : {
60 0 : const uint16_t* dp = d; // previous calculated raw
61 0 : s -= _w;
62 0 : d -= _w;
63 0 : uint16_t rawSum = 0;
64 0 : for( int32_t x = _w-1; x >= 0; x-- )
65 : {
66 0 : rawSum += s[x] > 0 ? 1 : 0;
67 0 : d[x] = dp[x] + rawSum;
68 : }
69 : }
70 0 : }
71 :
72 :
73 0 : inline uint16_t ROIEmptySpaceFinder::_getArea( const int32_t x, const int32_t y,
74 : const int32_t w, const int32_t h )
75 : const
76 : {
77 0 : return _getArea( w, h, &_data[0] + y * _w + x );
78 : }
79 :
80 0 : inline uint16_t ROIEmptySpaceFinder::_getArea( const int32_t w, const int32_t h,
81 : const uint16_t* data ) const
82 : {
83 0 : const uint16_t* data_ = data + h*_w;
84 0 : return *data - data[ w ] - *data_ + data_[ w ];
85 : }
86 :
87 :
88 0 : bool ROIEmptySpaceFinder::_updateMaximalEmptyRegion(
89 : const int32_t x, const int32_t y,
90 : const int32_t w, const int32_t h,
91 : PixelViewport& pvp,
92 : const uint16_t* data ) const
93 : {
94 0 : uint16_t maxArea = pvp.w * pvp.h;
95 0 : bool updated = false;
96 0 : int32_t maxW = 0;
97 0 : int32_t maxH = 0;
98 :
99 : // find biggest diagonal
100 0 : int32_t cwh = 2;
101 0 : while( cwh <= w && cwh <= h && _getArea( cwh, cwh, data ) == 0 )
102 0 : cwh++;
103 :
104 0 : cwh--;
105 :
106 0 : if( cwh*cwh > maxArea )
107 : {
108 0 : maxArea = cwh*cwh;
109 0 : maxW = cwh;
110 0 : maxH = cwh;
111 0 : updated = true;
112 : }
113 :
114 : // check parallelepipids
115 0 : if( cwh * w > maxArea )
116 : {
117 0 : int32_t ch = cwh;
118 0 : for( int32_t cw = cwh+1; cw <= w; cw++ )
119 : {
120 0 : while( _getArea( cw, ch, data ) != 0 )
121 : {
122 0 : ch--;
123 0 : if( ch == 0 )
124 : {
125 0 : cw = w + 1;
126 0 : break;
127 : }
128 : }
129 0 : if( cw*ch > maxArea )
130 : {
131 0 : maxArea = cw*ch;
132 0 : maxW = cw;
133 0 : maxH = ch;
134 0 : updated = true;
135 : }
136 : }
137 : }
138 :
139 0 : if( cwh * h > maxArea )
140 : {
141 0 : int32_t cw = cwh;
142 0 : for( int32_t ch = cwh+1; ch <= h; ch++ )
143 : {
144 0 : while( _getArea( cw, ch, data ) != 0 )
145 : {
146 0 : cw--;
147 0 : if( cw == 0 )
148 : {
149 0 : ch = h + 1;
150 0 : break;
151 : }
152 : }
153 0 : if( cw*ch > maxArea )
154 : {
155 0 : maxArea = cw*ch;
156 0 : maxW = cw;
157 0 : maxH = ch;
158 0 : updated = true;
159 : }
160 : }
161 : }
162 :
163 0 : if( updated )
164 0 : pvp = PixelViewport( x, y, maxW, maxH );
165 :
166 0 : return updated;
167 : }
168 :
169 0 : PixelViewport ROIEmptySpaceFinder::getLargestEmptyArea(const PixelViewport& pvp)
170 : const
171 : {
172 0 : LBASSERT( pvp.x >= 0 && pvp.w > 0 &&
173 : pvp.y >= 0 && pvp.h > 0 &&
174 : pvp.x + pvp.w < _w &&
175 : pvp.y + pvp.h < _h );
176 :
177 0 : LBASSERT( _mask );
178 :
179 0 : PixelViewport res( pvp.x, pvp.y, 0, 0 );
180 :
181 0 : uint16_t maxArea = _getArea( pvp.x, pvp.y, pvp.w, pvp.h );
182 0 : const uint16_t minRel = static_cast<uint16_t>( pvp.w * pvp.h * _limRel );
183 :
184 : // totally empty
185 0 : if( maxArea == 0 )
186 0 : return pvp;
187 :
188 : // totally full
189 0 : if( maxArea == pvp.w*pvp.h )
190 0 : return res;
191 :
192 : // over limit
193 0 : if( maxArea < _limAbs || maxArea < minRel )
194 0 : return res;
195 :
196 : // search for biggest empty pvp
197 0 : const uint16_t* data = &_data[0] + pvp.y * _w;
198 0 : const uint8_t* m = _mask + pvp.y * _w;
199 :
200 0 : maxArea = 0;
201 :
202 0 : for( int y=pvp.y, h=pvp.h; h > 0; y++, h-- )
203 : {
204 : // skeep if found area bigger than the rest of image
205 0 : if( h * pvp.w - _getArea( pvp.x, y, pvp.w, h ) <= maxArea )
206 0 : break;
207 :
208 0 : for( int x=pvp.x, w=pvp.w; w > 0; x++, w-- )
209 : {
210 : // skeep non empty blocks
211 0 : if( m[x] != 0 )
212 0 : continue;
213 :
214 : // skeep if found area bigger than the rest of image
215 0 : if( w*h - _getArea( w, h, data + x ) <= maxArea )
216 : {
217 0 : w = 0;
218 0 : continue;
219 : }
220 :
221 0 : if( _updateMaximalEmptyRegion( x, y, w, h, res, data + x ))
222 0 : maxArea = res.w * res.h;
223 : }
224 0 : m += _w;
225 0 : data += _w;
226 : }
227 :
228 0 : const uint16_t curArea = res.w * res.h;
229 0 : if( curArea < _limAbs || curArea < minRel )
230 0 : return PixelViewport( pvp.x, pvp.y, 0, 0 );
231 :
232 0 : return res;
233 : }
234 :
235 :
236 36 : }
|
