• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2011 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 // pyramid.cpp
18 
19 #include <stdio.h>
20 #include <string.h>
21 
22 #include "Pyramid.h"
23 
24 // We allocate the entire pyramid into one contiguous storage. This makes
25 // cleanup easier than fragmented stuff. In addition, we added a "pitch"
26 // field, so pointer manipulation is much simpler when it would be faster.
allocatePyramidPacked(real levels,real width,real height,real border)27 PyramidShort *PyramidShort::allocatePyramidPacked(real levels,
28         real width, real height, real border)
29 {
30     real border2 = (real) (border << 1);
31     int lines, size = calcStorage(width, height, border2, levels, &lines);
32 
33     PyramidShort *img = (PyramidShort *) calloc(sizeof(PyramidShort) * levels
34             + sizeof(short *) * lines +
35             + sizeof(short) * size, 1);
36 
37     if (img) {
38         PyramidShort *curr, *last;
39         ImageTypeShort *y = (ImageTypeShort *) &img[levels];
40         ImageTypeShort position = (ImageTypeShort) &y[lines];
41         for (last = (curr = img) + levels; curr < last; curr++) {
42             curr->width = width;
43             curr->height = height;
44             curr->border = border;
45             curr->pitch = (real) (width + border2);
46             curr->ptr = y + border;
47 
48             // Assign row pointers
49             for (int j = height + border2; j--; y++, position += curr->pitch) {
50                 *y = position + border;
51             }
52 
53             width >>= 1;
54             height >>= 1;
55         }
56     }
57 
58     return img;
59 }
60 
61 // Allocate an image of type short
allocateImage(real width,real height,real border)62 PyramidShort *PyramidShort::allocateImage(real width, real height, real border)
63 {
64     real border2 = (real) (border << 1);
65     PyramidShort *img = (PyramidShort *)
66         calloc(sizeof(PyramidShort) + sizeof(short *) * (height + border2) +
67                 sizeof(short) * (width + border2) * (height + border2), 1);
68 
69     if (img) {
70         short **y = (short **) &img[1];
71         short *position = (short *) &y[height + border2];
72         img->width = width;
73         img->height = height;
74         img->border = border;
75         img->pitch = (real) (width + border2);
76         img->ptr = y + border;
77         position += border; // Move position down to origin of real image
78 
79         // Assign row pointers
80         for (int j = height + border2; j--; y++, position += img->pitch) {
81             *y = position;
82         }
83     }
84 
85     return img;
86 }
87 
88 // Free the images
freeImage(PyramidShort * image)89 void PyramidShort::freeImage(PyramidShort *image)
90 {
91     if (image != NULL)
92         free(image);
93 }
94 
95 // Calculate amount of storage needed taking into account the borders, etc.
calcStorage(real width,real height,real border2,int levels,int * lines)96 unsigned int PyramidShort::calcStorage(real width, real height, real border2,   int levels, int *lines)
97 {
98     int size;
99 
100     *lines = size = 0;
101 
102     while(levels--) {
103         size += (width + border2) * (height + border2);
104         *lines += height + border2;
105         width >>= 1;
106         height >>= 1;
107     }
108 
109     return size;
110 }
111 
BorderSpread(PyramidShort * pyr,int left,int right,int top,int bot)112 void PyramidShort::BorderSpread(PyramidShort *pyr, int left, int right,
113         int top, int bot)
114 {
115     int off, off2, height, h, w;
116     ImageTypeShort base;
117 
118     if (left || right) {
119         off = pyr->border - left;
120         off2 = pyr->width + off + pyr->border - right - 1;
121         h = pyr->border - top;
122         height = pyr->height + (h << 1);
123         base = pyr->ptr[-h] - off;
124 
125         // spread in X
126         for (h = height; h--; base += pyr->pitch) {
127             for (w = left; w--;)
128                 base[-1 - w] = base[0];
129             for (w = right; w--;)
130                 base[off2 + w + 1] = base[off2];
131         }
132     }
133 
134     if (top || bot) {
135         // spread in Y
136         base = pyr->ptr[top - pyr->border] - pyr->border;
137         for (h = top; h--; base -= pyr->pitch) {
138             memcpy(base - pyr->pitch, base, pyr->pitch * sizeof(short));
139         }
140 
141         base = pyr->ptr[pyr->height + pyr->border - bot] - pyr->border;
142         for (h = bot; h--; base += pyr->pitch) {
143             memcpy(base, base - pyr->pitch, pyr->pitch * sizeof(short));
144         }
145     }
146 }
147 
BorderExpandOdd(PyramidShort * in,PyramidShort * out,PyramidShort * scr,int mode)148 void PyramidShort::BorderExpandOdd(PyramidShort *in, PyramidShort *out, PyramidShort *scr,
149         int mode)
150 {
151     int i,j;
152     int off = in->border / 2;
153 
154     // Vertical Filter
155     for (j = -off; j < in->height + off; j++) {
156         int j2 = j * 2;
157         int limit = scr->width + scr->border;
158         for (i = -scr->border; i < limit; i++) {
159             int t1 = in->ptr[j][i];
160             int t2 = in->ptr[j+1][i];
161             scr->ptr[j2][i] = (short)
162                 ((6 * t1 + (in->ptr[j-1][i] + t2) + 4) >> 3);
163             scr->ptr[j2+1][i] = (short)((t1 + t2 + 1) >> 1);
164         }
165     }
166 
167     BorderSpread(scr, 0, 0, 3, 3);
168 
169     // Horizontal Filter
170     int limit = out->height + out->border;
171     for (j = -out->border; j < limit; j++) {
172         for (i = -off; i < scr->width + off; i++) {
173             int i2 = i * 2;
174             int t1 = scr->ptr[j][i];
175             int t2 = scr->ptr[j][i+1];
176             out->ptr[j][i2] = (short) (out->ptr[j][i2] +
177                     (mode * ((6 * t1 +
178                               scr->ptr[j][i-1] + t2 + 4) >> 3)));
179             out->ptr[j][i2+1] = (short) (out->ptr[j][i2+1] +
180                     (mode * ((t1 + t2 + 1) >> 1)));
181         }
182     }
183 
184 }
185 
BorderExpand(PyramidShort * pyr,int nlev,int mode)186 int PyramidShort::BorderExpand(PyramidShort *pyr, int nlev, int mode)
187 {
188     PyramidShort *tpyr = pyr + nlev - 1;
189     PyramidShort *scr = allocateImage(pyr[1].width, pyr[0].height, pyr->border);
190     if (scr == NULL) return 0;
191 
192     if (mode > 0) {
193         // Expand and add (reconstruct from Laplacian)
194         for (; tpyr > pyr; tpyr--) {
195             scr->width = tpyr[0].width;
196             scr->height = tpyr[-1].height;
197             BorderExpandOdd(tpyr, tpyr - 1, scr, 1);
198         }
199     }
200     else if (mode < 0) {
201         // Expand and subtract (build Laplacian)
202         while ((pyr++) < tpyr) {
203             scr->width = pyr[0].width;
204             scr->height = pyr[-1].height;
205             BorderExpandOdd(pyr, pyr - 1, scr, -1);
206         }
207     }
208 
209     freeImage(scr);
210     return 1;
211 }
212 
BorderReduceOdd(PyramidShort * in,PyramidShort * out,PyramidShort * scr)213 void PyramidShort::BorderReduceOdd(PyramidShort *in, PyramidShort *out, PyramidShort *scr)
214 {
215     ImageTypeShortBase *s, *ns, *ls, *p, *np;
216 
217     int off = scr->border - 2;
218     s = scr->ptr[-scr->border] - (off >> 1);
219     ns = s + scr->pitch;
220     ls = scr->ptr[scr->height + scr->border - 1] + scr->pitch - (off >> 1);
221     int width = scr->width + scr->border;
222     p = in->ptr[-scr->border] - off;
223     np = p + in->pitch;
224 
225     // treat it as if the whole thing were the image
226     for (; s < ls; s = ns, ns += scr->pitch, p = np, np += in->pitch) {
227         for (int w = width; w--; s++, p += 2) {
228             *s = (short)((((int) p[-2]) + ((int) p[2]) + 8 +    // 1
229                         ((((int) p[-1]) + ((int) p[1])) << 2) + // 4
230                         ((int) *p) * 6) >> 4);          // 6
231         }
232     }
233 
234     BorderSpread(scr, 5, 4 + ((in->width ^ 1) & 1), 0, 0); //
235 
236     s = out->ptr[-(off >> 1)] - out->border;
237     ns = s + out->pitch;
238     ls = s + out->pitch * (out->height + off);
239     p = scr->ptr[-off] - out->border;
240     int pitch = scr->pitch;
241     int pitch2 = pitch << 1;
242     np = p + pitch2;
243     for (; s < ls; s = ns, ns += out->pitch, p = np, np += pitch2) {
244         for (int w = out->pitch; w--; s++, p++) {
245             *s = (short)((((int) p[-pitch2]) + ((int) p[pitch2]) + 8 + // 1
246                         ((((int) p[-pitch]) + ((int) p[pitch])) << 2) + // 4
247                         ((int) *p) * 6) >> 4);              // 6
248         }
249     }
250     BorderSpread(out, 0, 0, 5, 5);
251 
252 }
253 
BorderReduce(PyramidShort * pyr,int nlev)254 int PyramidShort::BorderReduce(PyramidShort *pyr, int nlev)
255 {
256     PyramidShort *scr = allocateImage(pyr[1].width, pyr[0].height, pyr->border);
257     if (scr == NULL)
258         return 0;
259 
260     BorderSpread(pyr, pyr->border, pyr->border, pyr->border, pyr->border);
261     while (--nlev) {
262         BorderReduceOdd(pyr, pyr + 1, scr);
263         pyr++;
264         scr->width = pyr[1].width;
265         scr->height = pyr[0].height;
266     }
267 
268     freeImage(scr);
269     return 1;
270 }
271