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 for (i = -scr->border; i < scr->width + scr->border; i++) { 158 scr->ptr[j2][i] = (short) 159 ((6 * in->ptr[j][i] + (in->ptr[j-1][i] + in->ptr[j+1][i]) + 4) >> 3); 160 scr->ptr[j2+1][i] = (short)((in->ptr[j][i] + in->ptr[j+1][i] + 1) >> 1); 161 } 162 } 163 164 BorderSpread(scr, 0, 0, 3, 3); 165 166 // Horizontal Filter 167 for (i = -off; i < scr->width + off; i++) { 168 int i2 = i * 2; 169 for (j = -out->border; j < out->height + out->border; j++) { 170 out->ptr[j][i2] = (short) (out->ptr[j][i2] + 171 (mode * ((6 * scr->ptr[j][i] + 172 scr->ptr[j][i-1] + scr->ptr[j][i+1] + 4) >> 3))); 173 out->ptr[j][i2+1] = (short) (out->ptr[j][i2+1] + 174 (mode * ((scr->ptr[j][i] + scr->ptr[j][i+1] + 1) >> 1))); 175 } 176 } 177 178 } 179 180 int PyramidShort::BorderExpand(PyramidShort *pyr, int nlev, int mode) 181 { 182 PyramidShort *tpyr = pyr + nlev - 1; 183 PyramidShort *scr = allocateImage(pyr[1].width, pyr[0].height, pyr->border); 184 if (scr == NULL) return 0; 185 186 if (mode > 0) { 187 // Expand and add (reconstruct from Laplacian) 188 for (; tpyr > pyr; tpyr--) { 189 scr->width = tpyr[0].width; 190 scr->height = tpyr[-1].height; 191 BorderExpandOdd(tpyr, tpyr - 1, scr, 1); 192 } 193 } 194 else if (mode < 0) { 195 // Expand and subtract (build Laplacian) 196 while ((pyr++) < tpyr) { 197 scr->width = pyr[0].width; 198 scr->height = pyr[-1].height; 199 BorderExpandOdd(pyr, pyr - 1, scr, -1); 200 } 201 } 202 203 freeImage(scr); 204 return 1; 205 } 206 207 void PyramidShort::BorderReduceOdd(PyramidShort *in, PyramidShort *out, PyramidShort *scr) 208 { 209 ImageTypeShortBase *s, *ns, *ls, *p, *np; 210 211 int off = scr->border - 2; 212 s = scr->ptr[-scr->border] - (off >> 1); 213 ns = s + scr->pitch; 214 ls = scr->ptr[scr->height + scr->border - 1] + scr->pitch - (off >> 1); 215 int width = scr->width + scr->border; 216 p = in->ptr[-scr->border] - off; 217 np = p + in->pitch; 218 219 // treat it as if the whole thing were the image 220 for (; s < ls; s = ns, ns += scr->pitch, p = np, np += in->pitch) { 221 for (int w = width; w--; s++, p += 2) { 222 *s = (short)((((int) p[-2]) + ((int) p[2]) + 8 + // 1 223 ((((int) p[-1]) + ((int) p[1])) << 2) + // 4 224 ((int) *p) * 6) >> 4); // 6 225 } 226 } 227 228 BorderSpread(scr, 5, 4 + ((in->width ^ 1) & 1), 0, 0); // 229 230 s = out->ptr[-(off >> 1)] - out->border; 231 ns = s + out->pitch; 232 ls = s + out->pitch * (out->height + off); 233 p = scr->ptr[-off] - out->border; 234 int pitch = scr->pitch; 235 int pitch2 = pitch << 1; 236 np = p + pitch2; 237 for (; s < ls; s = ns, ns += out->pitch, p = np, np += pitch2) { 238 for (int w = out->pitch; w--; s++, p++) { 239 *s = (short)((((int) p[-pitch2]) + ((int) p[pitch2]) + 8 + // 1 240 ((((int) p[-pitch]) + ((int) p[pitch])) << 2) + // 4 241 ((int) *p) * 6) >> 4); // 6 242 } 243 } 244 BorderSpread(out, 0, 0, 5, 5); 245 246 } 247 248 int PyramidShort::BorderReduce(PyramidShort *pyr, int nlev) 249 { 250 PyramidShort *scr = allocateImage(pyr[1].width, pyr[0].height, pyr->border); 251 if (scr == NULL) 252 return 0; 253 254 BorderSpread(pyr, pyr->border, pyr->border, pyr->border, pyr->border); 255 while (--nlev) { 256 BorderReduceOdd(pyr, pyr + 1, scr); 257 pyr++; 258 scr->width = pyr[1].width; 259 scr->height = pyr[0].height; 260 } 261 262 freeImage(scr); 263 return 1; 264 } 265
