1 /*=========================================================================
2 *
3 * Copyright Insight Software Consortium
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0.txt
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 *
17 *=========================================================================*/
18 #ifndef itkAnchorErodeDilateLine_hxx
19 #define itkAnchorErodeDilateLine_hxx
20
21 #include "itkAnchorErodeDilateLine.h"
22
23 namespace itk
24 {
25 template< typename TInputPix, typename TCompare >
26 AnchorErodeDilateLine< TInputPix, TCompare >
AnchorErodeDilateLine()27 ::AnchorErodeDilateLine()
28 {
29 m_Size = 2;
30 }
31
32 template< typename TInputPix, typename TCompare >
33 void
34 AnchorErodeDilateLine< TInputPix, TCompare >
DoLine(std::vector<TInputPix> & buffer,std::vector<TInputPix> & inbuffer,unsigned bufflength)35 ::DoLine(std::vector<TInputPix> & buffer, std::vector<TInputPix> & inbuffer, unsigned bufflength)
36 {
37 // TCompare will be < for erosions
38 // TFunction2 will be <=
39
40 // the initial version will adopt the methodology of loading a line
41 // at a time into a buffer vector, carrying out the opening or
42 // closing, and then copy the result to the output. Hopefully this
43 // will improve cache performance when working along non raster
44 // directions.
45 if ( bufflength <= m_Size / 2 )
46 {
47 // No point doing anything fancy - just look for the extreme value
48 // This is important when operating near the corner of images with
49 // angled structuring elements
50 InputImagePixelType Extreme = inbuffer[0];
51 for ( unsigned i = 0; i < bufflength; i++ )
52 {
53 if ( StrictCompare(Extreme, inbuffer[i]) )
54 {
55 Extreme = inbuffer[i];
56 }
57 }
58
59 for ( unsigned i = 0; i < bufflength; i++ )
60 {
61 buffer[i] = Extreme;
62 }
63 return;
64 }
65
66 int middle = (int)m_Size / 2;
67
68 int outLeftP = 0, outRightP = (int)bufflength - 1;
69 int inLeftP = 0, inRightP = (int)bufflength - 1;
70 InputImagePixelType Extreme;
71 HistogramType histo;
72 if ( bufflength <= m_Size )
73 {
74 // basically a standard histogram method
75 // Left border, first half of structuring element
76 Extreme = inbuffer[inLeftP];
77 histo.AddPixel(Extreme);
78 for ( int i = 0; ( i < middle ); i++ )
79 {
80 ++inLeftP;
81 histo.AddPixel(inbuffer[inLeftP]);
82 if ( StrictCompare(inbuffer[inLeftP], Extreme) )
83 {
84 Extreme = inbuffer[inLeftP];
85 }
86 }
87 buffer[outLeftP] = Extreme;
88
89 // Second half of SE
90 for ( int i = 0; i < (int)m_Size - middle - 1; i++ )
91 {
92 ++inLeftP;
93 ++outLeftP;
94 if ( inLeftP < (int)bufflength )
95 {
96 histo.AddPixel(inbuffer[inLeftP]);
97 if ( StrictCompare(inbuffer[inLeftP], Extreme) )
98 {
99 Extreme = inbuffer[inLeftP];
100 }
101 }
102 buffer[outLeftP] = Extreme;
103 }
104 // now finish
105 outLeftP++;
106 int left = 0;
107 for (; outLeftP < (int)bufflength; outLeftP++, left++ )
108 {
109 histo.RemovePixel(inbuffer[left]);
110 Extreme = histo.GetValue();
111 buffer[outLeftP] = Extreme;
112 }
113 return;
114 }
115
116 // Left border, first half of structuring element
117 Extreme = inbuffer[inLeftP];
118 histo.AddPixel(Extreme);
119 for ( int i = 0; ( i < middle ); i++ )
120 {
121 ++inLeftP;
122 histo.AddPixel(inbuffer[inLeftP]);
123 if ( StrictCompare(inbuffer[inLeftP], Extreme) )
124 {
125 Extreme = inbuffer[inLeftP];
126 }
127 }
128 buffer[outLeftP] = Extreme;
129
130 // Second half of SE
131 for ( int i = 0; i < (int)m_Size - middle - 1; i++ )
132 {
133 ++inLeftP;
134 ++outLeftP;
135 histo.AddPixel(inbuffer[inLeftP]);
136 if ( StrictCompare(inbuffer[inLeftP], Extreme) )
137 {
138 Extreme = inbuffer[inLeftP];
139 }
140 buffer[outLeftP] = Extreme;
141 }
142 // Use the histogram until we find a new minimum
143 while ( ( inLeftP < inRightP ) && Compare(Extreme, inbuffer[inLeftP + 1]) )
144 {
145 ++inLeftP;
146 ++outLeftP;
147
148 histo.RemovePixel(inbuffer[inLeftP - (int)m_Size]);
149 histo.AddPixel(inbuffer[inLeftP]);
150 Extreme = histo.GetValue();
151 buffer[outLeftP] = Extreme;
152 }
153 Extreme = buffer[outLeftP];
154
155 while ( StartLine(buffer,
156 inbuffer,
157 Extreme,
158 outLeftP,
159 outRightP,
160 inLeftP,
161 inRightP,
162 middle) )
163 {}
164
165 FinishLine(buffer,
166 inbuffer,
167 Extreme,
168 outLeftP,
169 outRightP,
170 inLeftP,
171 inRightP,
172 middle);
173 }
174
175 template< typename TInputPix, typename TCompare >
176 bool
177 AnchorErodeDilateLine< TInputPix, TCompare >
StartLine(std::vector<TInputPix> & buffer,std::vector<TInputPix> & inbuffer,InputImagePixelType & Extreme,int & outLeftP,int & itkNotUsed (outRightP),int & inLeftP,int & inRightP,int itkNotUsed (middle))178 ::StartLine(std::vector<TInputPix> & buffer,
179 std::vector<TInputPix> & inbuffer,
180 InputImagePixelType & Extreme,
181 int & outLeftP,
182 int & itkNotUsed(outRightP),
183 int & inLeftP,
184 int & inRightP,
185 int itkNotUsed(middle)
186 )
187 {
188 // This returns true to indicate return to startLine label in pseudo
189 // code, and false to indicate finshLine
190 int currentP = inLeftP + 1;
191 int sentinel;
192
193 while ( ( currentP < inRightP ) && Compare(inbuffer[currentP], Extreme) )
194 {
195 Extreme = inbuffer[currentP];
196 ++outLeftP;
197 buffer[outLeftP] = Extreme;
198 ++currentP;
199 }
200 inLeftP = currentP - 1;
201
202 sentinel = inLeftP + (int)m_Size;
203 if ( sentinel > inRightP )
204 {
205 // finish
206 return ( false );
207 }
208 ++outLeftP;
209 buffer[outLeftP] = Extreme;
210
211 // ran m_Size pixels ahead
212 ++currentP;
213 while ( currentP < sentinel )
214 {
215 if ( Compare(inbuffer[currentP], Extreme) )
216 {
217 Extreme = inbuffer[currentP];
218 ++outLeftP;
219 buffer[outLeftP] = Extreme;
220 inLeftP = currentP;
221 return ( true );
222 }
223 ++currentP;
224 ++outLeftP;
225 buffer[outLeftP] = Extreme;
226 }
227 // We didn't find a smaller (for erosion) value in the segment of
228 // reach of inLeftP. currentP is the first position outside the
229 // reach of inLeftP
230 HistogramType histo;
231 if ( Compare(inbuffer[currentP], Extreme) )
232 {
233 Extreme = inbuffer[currentP];
234 ++outLeftP;
235 buffer[outLeftP] = Extreme;
236 inLeftP = currentP;
237 return ( true );
238 }
239 else
240 {
241 // Now we need a histogram
242 // Initialise it
243 ++outLeftP;
244 ++inLeftP;
245 for ( int aux = inLeftP; aux <= currentP; ++aux )
246 {
247 histo.AddPixel(inbuffer[aux]);
248 }
249 Extreme = histo.GetValue();
250 buffer[outLeftP] = Extreme;
251 }
252
253 while ( currentP < inRightP )
254 {
255 ++currentP;
256 if ( Compare(inbuffer[currentP], Extreme) )
257 {
258 // Found a new extrem
259 Extreme = inbuffer[currentP];
260 ++outLeftP;
261 buffer[outLeftP] = Extreme;
262 inLeftP = currentP;
263 return ( true );
264 }
265 else
266 {
267 // update histogram
268 histo.AddPixel(inbuffer[currentP]);
269 histo.RemovePixel(inbuffer[inLeftP]);
270 // find extreme
271 Extreme = histo.GetValue();
272 ++inLeftP;
273 ++outLeftP;
274 buffer[outLeftP] = Extreme;
275 }
276 }
277 return ( false );
278 }
279
280 template< typename TInputPix, typename TCompare >
281 void
282 AnchorErodeDilateLine< TInputPix, TCompare >
FinishLine(std::vector<TInputPix> & buffer,std::vector<TInputPix> & inbuffer,InputImagePixelType & Extreme,int & outLeftP,int & outRightP,int & itkNotUsed (inLeftP),int & inRightP,int middle)283 ::FinishLine(std::vector<TInputPix> & buffer,
284 std::vector<TInputPix> & inbuffer,
285 InputImagePixelType & Extreme,
286 int & outLeftP,
287 int & outRightP,
288 int & itkNotUsed(inLeftP),
289 int & inRightP,
290 int middle
291 )
292 {
293 // Handles the right border.
294 // First half of the structuring element
295 HistogramType histo;
296 Extreme = inbuffer[inRightP];
297 histo.AddPixel(Extreme);
298
299 for ( int i = 0; i < middle; i++ )
300 {
301 --inRightP;
302 histo.AddPixel(inbuffer[inRightP]);
303 if ( StrictCompare(inbuffer[inRightP], Extreme) )
304 {
305 Extreme = inbuffer[inRightP];
306 }
307 }
308 buffer[outRightP] = Extreme;
309 // second half of SE
310 for ( int i = 0; ( i < (int)m_Size - middle - 1 ) && ( outLeftP < outRightP ); i++ )
311 {
312 --inRightP;
313 --outRightP;
314 histo.AddPixel(inbuffer[inRightP]);
315 if ( StrictCompare(inbuffer[inRightP], Extreme) )
316 {
317 Extreme = inbuffer[inRightP];
318 }
319 buffer[outRightP] = Extreme;
320 }
321
322 while ( outLeftP < outRightP )
323 {
324 --inRightP;
325 --outRightP;
326 histo.RemovePixel(inbuffer[inRightP + (int)m_Size]);
327 histo.AddPixel(inbuffer[inRightP]);
328 if ( StrictCompare(inbuffer[inRightP], Extreme) )
329 {
330 Extreme = inbuffer[inRightP];
331 }
332 Extreme = histo.GetValue();
333 buffer[outRightP] = Extreme;
334 }
335 }
336
337 template< typename TInputPix, typename TCompare >
338 void
339 AnchorErodeDilateLine< TInputPix, TCompare >
PrintSelf(std::ostream & os,Indent indent) const340 ::PrintSelf(std::ostream & os, Indent indent) const
341 {
342 os << indent << "Size: " << m_Size << std::endl;
343 }
344 } // end namespace itk
345
346 #endif
347