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. 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 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 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. 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 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 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 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 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 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
