| /*====================================================================* |
| - Copyright (C) 2001 Leptonica. All rights reserved. |
| - This software is distributed in the hope that it will be |
| - useful, but with NO WARRANTY OF ANY KIND. |
| - No author or distributor accepts responsibility to anyone for the |
| - consequences of using this software, or for whether it serves any |
| - particular purpose or works at all, unless he or she says so in |
| - writing. Everyone is granted permission to copy, modify and |
| - redistribute this source code, for commercial or non-commercial |
| - purposes, with the following restrictions: (1) the origin of this |
| - source code must not be misrepresented; (2) modified versions must |
| - be plainly marked as such; and (3) this notice may not be removed |
| - or altered from any source or modified source distribution. |
| *====================================================================*/ |
| |
| /* |
| * seedfilllow.c |
| * |
| * Seedfill: |
| * Gray seedfill (source: Luc Vincent:fast-hybrid-grayscale-reconstruction) |
| * void seedfillBinaryLow() |
| * void seedfillGrayLow() |
| * void seedfillGrayInvLow() |
| * void seedfillGrayLowSimple() |
| * void seedfillGrayInvLowSimple() |
| * |
| * Distance function: |
| * void distanceFunctionLow() |
| * |
| * Seed spread: |
| * void seedspreadLow() |
| * |
| */ |
| |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <math.h> |
| #include "allheaders.h" |
| |
| struct L_Pixel |
| { |
| l_int32 x; |
| l_int32 y; |
| }; |
| typedef struct L_Pixel L_PIXEL; |
| |
| |
| /*-----------------------------------------------------------------------* |
| * Vincent's Iterative Binary Seedfill * |
| *-----------------------------------------------------------------------*/ |
| /*! |
| * seedfillBinaryLow() |
| * |
| * Notes: |
| * (1) This is an in-place fill, where the seed image is |
| * filled, clipping to the filling mask, in one full |
| * cycle of UL -> LR and LR -> UL raster scans. |
| * (2) Assume the mask is a filling mask, not a blocking mask. |
| * (3) Assume that the RHS pad bits of the mask |
| * are properly set to 0. |
| * (4) Clip to the smallest dimensions to avoid invalid reads. |
| */ |
| void |
| seedfillBinaryLow(l_uint32 *datas, |
| l_int32 hs, |
| l_int32 wpls, |
| l_uint32 *datam, |
| l_int32 hm, |
| l_int32 wplm, |
| l_int32 connectivity) |
| { |
| l_int32 i, j, h, wpl; |
| l_uint32 word, mask; |
| l_uint32 wordabove, wordleft, wordbelow, wordright; |
| l_uint32 wordprev; /* test against this in previous iteration */ |
| l_uint32 *lines, *linem; |
| |
| PROCNAME("seedfillBinaryLow"); |
| |
| h = L_MIN(hs, hm); |
| wpl = L_MIN(wpls, wplm); |
| |
| switch (connectivity) |
| { |
| case 4: |
| /* UL --> LR scan */ |
| for (i = 0; i < h; i++) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = 0; j < wpl; j++) { |
| word = *(lines + j); |
| mask = *(linem + j); |
| |
| /* OR from word above and from word to left; mask */ |
| if (i > 0) { |
| wordabove = *(lines - wpls + j); |
| word |= wordabove; |
| } |
| if (j > 0) { |
| wordleft = *(lines + j - 1); |
| word |= wordleft << 31; |
| } |
| word &= mask; |
| |
| /* No need to fill horizontally? */ |
| if (!word || !(~word)) { |
| *(lines + j) = word; |
| continue; |
| } |
| |
| while (1) { |
| wordprev = word; |
| word = (word | (word >> 1) | (word << 1)) & mask; |
| if ((word ^ wordprev) == 0) { |
| *(lines + j) = word; |
| break; |
| } |
| } |
| } |
| } |
| |
| /* LR --> UL scan */ |
| for (i = h - 1; i >= 0; i--) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = wpl - 1; j >= 0; j--) { |
| word = *(lines + j); |
| mask = *(linem + j); |
| |
| /* OR from word below and from word to right; mask */ |
| if (i < h - 1) { |
| wordbelow = *(lines + wpls + j); |
| word |= wordbelow; |
| } |
| if (j < wpl - 1) { |
| wordright = *(lines + j + 1); |
| word |= wordright >> 31; |
| } |
| word &= mask; |
| |
| /* No need to fill horizontally? */ |
| if (!word || !(~word)) { |
| *(lines + j) = word; |
| continue; |
| } |
| |
| while (1) { |
| wordprev = word; |
| word = (word | (word >> 1) | (word << 1)) & mask; |
| if ((word ^ wordprev) == 0) { |
| *(lines + j) = word; |
| break; |
| } |
| } |
| } |
| } |
| break; |
| |
| case 8: |
| /* UL --> LR scan */ |
| for (i = 0; i < h; i++) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = 0; j < wpl; j++) { |
| word = *(lines + j); |
| mask = *(linem + j); |
| |
| /* OR from words above and from word to left; mask */ |
| if (i > 0) { |
| wordabove = *(lines - wpls + j); |
| word |= (wordabove | (wordabove << 1) | (wordabove >> 1)); |
| if (j > 0) |
| word |= (*(lines - wpls + j - 1)) << 31; |
| if (j < wpl - 1) |
| word |= (*(lines - wpls + j + 1)) >> 31; |
| } |
| if (j > 0) { |
| wordleft = *(lines + j - 1); |
| word |= wordleft << 31; |
| } |
| word &= mask; |
| |
| /* No need to fill horizontally? */ |
| if (!word || !(~word)) { |
| *(lines + j) = word; |
| continue; |
| } |
| |
| while (1) { |
| wordprev = word; |
| word = (word | (word >> 1) | (word << 1)) & mask; |
| if ((word ^ wordprev) == 0) { |
| *(lines + j) = word; |
| break; |
| } |
| } |
| } |
| } |
| |
| /* LR --> UL scan */ |
| for (i = h - 1; i >= 0; i--) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = wpl - 1; j >= 0; j--) { |
| word = *(lines + j); |
| mask = *(linem + j); |
| |
| /* OR from words below and from word to right; mask */ |
| if (i < h - 1) { |
| wordbelow = *(lines + wpls + j); |
| word |= (wordbelow | (wordbelow << 1) | (wordbelow >> 1)); |
| if (j > 0) |
| word |= (*(lines + wpls + j - 1)) << 31; |
| if (j < wpl - 1) |
| word |= (*(lines + wpls + j + 1)) >> 31; |
| } |
| if (j < wpl - 1) { |
| wordright = *(lines + j + 1); |
| word |= wordright >> 31; |
| } |
| word &= mask; |
| |
| /* No need to fill horizontally? */ |
| if (!word || !(~word)) { |
| *(lines + j) = word; |
| continue; |
| } |
| |
| while (1) { |
| wordprev = word; |
| word = (word | (word >> 1) | (word << 1)) & mask; |
| if ((word ^ wordprev) == 0) { |
| *(lines + j) = word; |
| break; |
| } |
| } |
| } |
| } |
| break; |
| |
| default: |
| ERROR_VOID("connectivity must be 4 or 8", procName); |
| } |
| |
| return; |
| } |
| |
| |
| |
| /*-----------------------------------------------------------------------* |
| * Vincent's Hybrid Grayscale Seedfill * |
| *-----------------------------------------------------------------------*/ |
| /*! |
| * seedfillGrayLow() |
| * |
| * Notes: |
| * (1) The pixels are numbered as follows: |
| * 1 2 3 |
| * 4 x 5 |
| * 6 7 8 |
| * This low-level filling operation consists of two scans, |
| * raster and anti-raster, covering the entire seed image. |
| * This is followed by a breadth-first propagation operation to |
| * complete the fill. |
| * During the anti-raster scan, every pixel p whose current value |
| * could still be propagated after the anti-raster scan is put into |
| * the FIFO queue. |
| * The propagation step is a breadth-first fill to completion. |
| * Unlike the simple grayscale seedfill pixSeedfillGraySimple(), |
| * where at least two full raster/anti-raster iterations are required |
| * for completion and verification, the hybrid method uses only a |
| * single raster/anti-raster set of scans. |
| * (2) The filling action can be visualized from the following example. |
| * Suppose the mask, which clips the fill, is a sombrero-shaped |
| * surface, where the highest point is 200 and the low pixels |
| * around the rim are 30. Beyond the rim, the mask goes up a bit. |
| * Suppose the seed, which is filled, consists of a single point |
| * of height 150, located below the max of the mask, with |
| * the rest 0. Then in the raster scan, nothing happens until |
| * the high seed point is encountered, and then this value is |
| * propagated right and down, until it hits the side of the |
| * sombrero. The seed can never exceed the mask, so it fills |
| * to the rim, going lower along the mask surface. When it |
| * passes the rim, the seed continues to fill at the rim |
| * height to the edge of the seed image. Then on the |
| * anti-raster scan, the seed fills flat inside the |
| * sombrero to the upper and left, and then out from the |
| * rim as before. The final result has a seed that is |
| * flat outside the rim, and inside it fills the sombrero |
| * but only up to 150. If the rim height varies, the |
| * filled seed outside the rim will be at the highest |
| * point on the rim, which is a saddle point on the rim. |
| * (3) Reference paper : |
| * L. Vincent, Morphological grayscale reconstruction in image |
| * analysis: applications and efficient algorithms, IEEE Transactions |
| * on Image Processing, vol. 2, no. 2, pp. 176-201, 1993. |
| */ |
| void |
| seedfillGrayLow(l_uint32 *datas, |
| l_int32 w, |
| l_int32 h, |
| l_int32 wpls, |
| l_uint32 *datam, |
| l_int32 wplm, |
| l_int32 connectivity) |
| { |
| l_uint8 val1, val2, val3, val4, val5, val6, val7, val8; |
| l_uint8 val, maxval, maskval, boolval; |
| l_int32 i, j, imax, jmax, queue_size; |
| l_uint32 *lines, *linem; |
| L_PIXEL *pixel; |
| L_QUEUE *lq_pixel; |
| |
| PROCNAME("seedfillGrayLow"); |
| |
| imax = h - 1; |
| jmax = w - 1; |
| |
| /* In the worst case, most of the pixels could be pushed |
| * onto the FIFO queue during anti-raster scan. However this |
| * will rarely happen, and we initialize the queue ptr size to |
| * the image perimeter. */ |
| lq_pixel = lqueueCreate(2 * (w + h)); |
| |
| switch (connectivity) |
| { |
| case 4: |
| /* UL --> LR scan (Raster Order) |
| * If I : mask image |
| * J : marker image |
| * Let p be the currect pixel; |
| * J(p) <- (max{J(p) union J(p) neighbors in raster order}) |
| * intersection I(p) */ |
| for (i = 0; i < h; i++) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = 0; j < w; j++) { |
| if ((maskval = GET_DATA_BYTE(linem, j)) > 0) { |
| maxval = 0; |
| if (i > 0) |
| maxval = GET_DATA_BYTE(lines - wpls, j); |
| if (j > 0) { |
| val4 = GET_DATA_BYTE(lines, j - 1); |
| maxval = L_MAX(maxval, val4); |
| } |
| val = GET_DATA_BYTE(lines, j); |
| maxval = L_MAX(maxval, val); |
| val = L_MIN(maxval, maskval); |
| SET_DATA_BYTE(lines, j, val); |
| } |
| } |
| } |
| |
| /* LR --> UL scan (anti-raster order) |
| * Let p be the currect pixel; |
| * J(p) <- (max{J(p) union J(p) neighbors in anti-raster order}) |
| * intersection I(p) */ |
| for (i = imax; i >= 0; i--) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = jmax; j >= 0; j--) { |
| boolval = FALSE; |
| if ((maskval = GET_DATA_BYTE(linem, j)) > 0) { |
| maxval = 0; |
| if (i < imax) |
| maxval = GET_DATA_BYTE(lines + wpls, j); |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| maxval = L_MAX(maxval, val5); |
| } |
| val = GET_DATA_BYTE(lines, j); |
| maxval = L_MAX(maxval, val); |
| val = L_MIN(maxval, maskval); |
| SET_DATA_BYTE(lines, j, val); |
| |
| /* |
| * If there exists a point (q) which belongs to J(p) |
| * neighbors in anti-raster order such that J(q) < J(p) |
| * and J(q) < I(q) then |
| * fifo_add(p) */ |
| if (i < imax) { |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| if ((val7 < val) && |
| (val7 < GET_DATA_BYTE(linem + wplm, j))) { |
| boolval = TRUE; |
| } |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| if (!boolval && (val5 < val) && |
| (val5 < GET_DATA_BYTE(linem, j + 1))) { |
| boolval = TRUE; |
| } |
| } |
| if (boolval) { |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i; |
| pixel->y = j; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| } |
| } |
| |
| /* Propagation step: |
| * while fifo_empty = false |
| * p <- fifo_first() |
| * for every pixel (q) belong to neighbors of (p) |
| * if J(q) < J(p) and I(q) != J(q) |
| * J(q) <- min(J(p), I(q)); |
| * fifo_add(q); |
| * end |
| * end |
| * end */ |
| queue_size = lqueueGetCount(lq_pixel); |
| while (queue_size) { |
| pixel = (L_PIXEL *)lqueueRemove(lq_pixel); |
| i = pixel->x; |
| j = pixel->y; |
| FREE(pixel); |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| |
| if ((val = GET_DATA_BYTE(lines, j)) > 0) { |
| if (i > 0) { |
| val2 = GET_DATA_BYTE(lines - wpls, j); |
| maskval = GET_DATA_BYTE(linem - wplm, j); |
| if (val > val2 && val2 != maskval) { |
| SET_DATA_BYTE(lines - wpls, j, L_MIN(val, maskval)); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i - 1; |
| pixel->y = j; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| |
| } |
| if (j > 0) { |
| val4 = GET_DATA_BYTE(lines, j - 1); |
| maskval = GET_DATA_BYTE(linem, j - 1); |
| if (val > val4 && val4 != maskval) { |
| SET_DATA_BYTE(lines, j - 1, L_MIN(val, maskval)); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i; |
| pixel->y = j - 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| if (i < imax) { |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| maskval = GET_DATA_BYTE(linem + wplm, j); |
| if (val > val7 && val7 != maskval) { |
| SET_DATA_BYTE(lines + wpls, j, L_MIN(val, maskval)); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i + 1; |
| pixel->y = j; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| maskval = GET_DATA_BYTE(linem, j + 1); |
| if (val > val5 && val5 != maskval) { |
| SET_DATA_BYTE(lines, j + 1, L_MIN(val, maskval)); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i; |
| pixel->y = j + 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| } |
| |
| queue_size = lqueueGetCount(lq_pixel); |
| } |
| |
| break; |
| |
| case 8: |
| /* UL --> LR scan (Raster Order) |
| * If I : mask image |
| * J : marker image |
| * Let p be the currect pixel; |
| * J(p) <- (max{J(p) union J(p) neighbors in raster order}) |
| * intersection I(p) */ |
| for (i = 0; i < h; i++) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = 0; j < w; j++) { |
| if ((maskval = GET_DATA_BYTE(linem, j)) > 0) { |
| maxval = 0; |
| if (i > 0) { |
| if (j > 0) |
| maxval = GET_DATA_BYTE(lines - wpls, j - 1); |
| if (j < jmax) { |
| val3 = GET_DATA_BYTE(lines - wpls, j + 1); |
| maxval = L_MAX(maxval, val3); |
| } |
| val2 = GET_DATA_BYTE(lines - wpls, j); |
| maxval = L_MAX(maxval, val2); |
| } |
| if (j > 0) { |
| val4 = GET_DATA_BYTE(lines, j - 1); |
| maxval = L_MAX(maxval, val4); |
| } |
| val = GET_DATA_BYTE(lines, j); |
| maxval = L_MAX(maxval, val); |
| val = L_MIN(maxval, maskval); |
| SET_DATA_BYTE(lines, j, val); |
| } |
| } |
| } |
| |
| /* LR --> UL scan (anti-raster order) |
| * Let p be the currect pixel; |
| * J(p) <- (max{J(p) union J(p) neighbors in anti-raster order}) |
| * intersection I(p) */ |
| for (i = imax; i >= 0; i--) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = jmax; j >= 0; j--) { |
| boolval = FALSE; |
| if ((maskval = GET_DATA_BYTE(linem, j)) > 0) { |
| maxval = 0; |
| if (i < imax) { |
| if (j > 0) { |
| maxval = GET_DATA_BYTE(lines + wpls, j - 1); |
| } |
| if (j < jmax) { |
| val8 = GET_DATA_BYTE(lines + wpls, j + 1); |
| maxval = L_MAX(maxval, val8); |
| } |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| maxval = L_MAX(maxval, val7); |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| maxval = L_MAX(maxval, val5); |
| } |
| val = GET_DATA_BYTE(lines, j); |
| maxval = L_MAX(maxval, val); |
| val = L_MIN(maxval, maskval); |
| SET_DATA_BYTE(lines, j, val); |
| |
| /* If there exists a point (q) which belongs to J(p) |
| * neighbors in anti-raster order such that J(q) < J(p) |
| * and J(q) < I(q) then |
| * fifo_add(p) */ |
| if (i < imax) { |
| if (j > 0) { |
| val6 = GET_DATA_BYTE(lines + wpls, j - 1); |
| if ((val6 < val) && |
| (val6 < GET_DATA_BYTE(linem + wplm, j - 1))) { |
| boolval = TRUE; |
| } |
| } |
| if (j < jmax) { |
| val8 = GET_DATA_BYTE(lines + wpls, j + 1); |
| if (!boolval && (val8 < val) && |
| (val8 < GET_DATA_BYTE(linem + wplm, j + 1))) { |
| boolval = TRUE; |
| } |
| } |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| if (!boolval && (val7 < val) && |
| (val7 < GET_DATA_BYTE(linem + wplm, j))) { |
| boolval = TRUE; |
| } |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| if (!boolval && (val5 < val) && |
| (val5 < GET_DATA_BYTE(linem, j + 1))) { |
| boolval = TRUE; |
| } |
| } |
| if (boolval) { |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i; |
| pixel->y = j; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| } |
| } |
| |
| /* Propagation step: |
| * while fifo_empty = false |
| * p <- fifo_first() |
| * for every pixel (q) belong to neighbors of (p) |
| * if J(q) < J(p) and I(q) != J(q) |
| * J(q) <- min(J(p), I(q)); |
| * fifo_add(q); |
| * end |
| * end |
| * end */ |
| queue_size = lqueueGetCount(lq_pixel); |
| while (queue_size) { |
| pixel = (L_PIXEL *)lqueueRemove(lq_pixel); |
| i = pixel->x; |
| j = pixel->y; |
| FREE(pixel); |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| |
| if ((val = GET_DATA_BYTE(lines, j)) > 0) { |
| if (i > 0) { |
| if (j > 0) { |
| val1 = GET_DATA_BYTE(lines - wpls, j - 1); |
| maskval = GET_DATA_BYTE(linem - wplm, j - 1); |
| if (val > val1 && val1 != maskval) { |
| SET_DATA_BYTE(lines - wpls, j - 1, L_MIN(val, maskval)); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i - 1; |
| pixel->y = j - 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| if (j < jmax) { |
| val3 = GET_DATA_BYTE(lines - wpls, j + 1); |
| maskval = GET_DATA_BYTE(linem - wplm, j + 1); |
| if (val > val3 && val3 != maskval) { |
| SET_DATA_BYTE(lines - wpls, j + 1, L_MIN(val, maskval)); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i - 1; |
| pixel->y = j + 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| val2 = GET_DATA_BYTE(lines - wpls, j); |
| maskval = GET_DATA_BYTE(linem - wplm, j); |
| if (val > val2 && val2 != maskval) { |
| SET_DATA_BYTE(lines - wpls, j, L_MIN(val, maskval)); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i - 1; |
| pixel->y = j; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| |
| } |
| if (j > 0) { |
| val4 = GET_DATA_BYTE(lines, j - 1); |
| maskval = GET_DATA_BYTE(linem, j - 1); |
| if (val > val4 && val4 != maskval) { |
| SET_DATA_BYTE(lines, j - 1, L_MIN(val, maskval)); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i; |
| pixel->y = j - 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| if (i < imax) { |
| if (j > 0) { |
| val6 = GET_DATA_BYTE(lines + wpls, j - 1); |
| maskval = GET_DATA_BYTE(linem + wplm, j - 1); |
| if (val > val6 && val6 != maskval) { |
| SET_DATA_BYTE(lines + wpls, j - 1, L_MIN(val, maskval)); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i + 1; |
| pixel->y = j - 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| if (j < jmax) { |
| val8 = GET_DATA_BYTE(lines + wpls, j + 1); |
| maskval = GET_DATA_BYTE(linem + wplm, j + 1); |
| if (val > val8 && val8 != maskval) { |
| SET_DATA_BYTE(lines + wpls, j + 1, L_MIN(val, maskval)); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i + 1; |
| pixel->y = j + 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| maskval = GET_DATA_BYTE(linem + wplm, j); |
| if (val > val7 && val7 != maskval) { |
| SET_DATA_BYTE(lines + wpls, j, L_MIN(val, maskval)); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i + 1; |
| pixel->y = j; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| maskval = GET_DATA_BYTE(linem, j + 1); |
| if (val > val5 && val5 != maskval) { |
| SET_DATA_BYTE(lines, j + 1, L_MIN(val, maskval)); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i; |
| pixel->y = j + 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| } |
| |
| queue_size = lqueueGetCount(lq_pixel); |
| } |
| break; |
| |
| default: |
| ERROR_VOID("connectivity must be 4 or 8", procName); |
| lqueueDestroy(&lq_pixel, TRUE); |
| } |
| |
| lqueueDestroy(&lq_pixel, TRUE); |
| return; |
| } |
| |
| |
| /*! |
| * seedfillGrayInvLow() |
| * |
| * Notes: |
| * (1) The pixels are numbered as follows: |
| * 1 2 3 |
| * 4 x 5 |
| * 6 7 8 |
| * This low-level filling operation consists of two scans, |
| * raster and anti-raster, covering the entire seed image. |
| * During the anti-raster scan, every pixel p such that its |
| * current value could still be propogated during the next |
| * raster scanning is put into the FIFO-queue. |
| * Next step is the propagation step where where we update |
| * and propagate the values using FIFO structure created in |
| * anti-raster scan. |
| * (2) The "Inv" signifies the fact that in this case, filling |
| * of the seed only takes place when the seed value is |
| * greater than the mask value. The mask will act to stop |
| * the fill when it is higher than the seed level. (This is |
| * in contrast to conventional grayscale filling where the |
| * seed always fills below the mask.) |
| * (3) An example of use is a basin, described by the mask (pixm), |
| * where within the basin, the seed pix (pixs) gets filled to the |
| * height of the highest seed pixel that is above its |
| * corresponding max pixel. Filling occurs while the |
| * propagating seed pixels in pixs are larger than the |
| * corresponding mask values in pixm. |
| * (4) Reference paper : |
| * L. Vincent, Morphological grayscale reconstruction in image |
| * analysis: applications and efficient algorithms, IEEE Transactions |
| * on Image Processing, vol. 2, no. 2, pp. 176-201, 1993. |
| */ |
| void |
| seedfillGrayInvLow(l_uint32 *datas, |
| l_int32 w, |
| l_int32 h, |
| l_int32 wpls, |
| l_uint32 *datam, |
| l_int32 wplm, |
| l_int32 connectivity) |
| { |
| l_uint8 val1, val2, val3, val4, val5, val6, val7, val8; |
| l_uint8 val, maxval, maskval, boolval; |
| l_int32 i, j, imax, jmax, queue_size; |
| l_uint32 *lines, *linem; |
| L_PIXEL *pixel; |
| L_QUEUE *lq_pixel; |
| |
| PROCNAME("seedfillGrayInvLow"); |
| |
| imax = h - 1; |
| jmax = w - 1; |
| |
| /* In the worst case, most of the pixels could be pushed |
| * onto the FIFO queue during anti-raster scan. However this |
| * will rarely happen, and we initialize the queue ptr size to |
| * the image perimeter. */ |
| lq_pixel = lqueueCreate(2 * (w + h)); |
| |
| switch (connectivity) |
| { |
| case 4: |
| /* UL --> LR scan (Raster Order) |
| * If I : mask image |
| * J : marker image |
| * Let p be the currect pixel; |
| * tmp <- max{J(p) union J(p) neighbors in raster order} |
| * if (tmp > I(p)) |
| * J(p) <- tmp |
| * end */ |
| for (i = 0; i < h; i++) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = 0; j < w; j++) { |
| if ((maskval = GET_DATA_BYTE(linem, j)) < 255) { |
| maxval = GET_DATA_BYTE(lines, j); |
| if (i > 0) { |
| val2 = GET_DATA_BYTE(lines - wpls, j); |
| maxval = L_MAX(maxval, val2); |
| } |
| if (j > 0) { |
| val4 = GET_DATA_BYTE(lines, j - 1); |
| maxval = L_MAX(maxval, val4); |
| } |
| if (maxval > maskval) |
| SET_DATA_BYTE(lines, j, maxval); |
| } |
| } |
| } |
| |
| /* LR --> UL scan (anti-raster order) |
| * If I : mask image |
| * J : marker image |
| * Let p be the currect pixel; |
| * tmp <- max{J(p) union J(p) neighbors in anti-raster order} |
| * if (tmp > I(p)) |
| * J(p) <- tmp |
| * end */ |
| for (i = imax; i >= 0; i--) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = jmax; j >= 0; j--) { |
| boolval = FALSE; |
| if ((maskval = GET_DATA_BYTE(linem, j)) < 255) { |
| val = maxval = GET_DATA_BYTE(lines, j); |
| if (i < imax) { |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| maxval = L_MAX(maxval, val7); |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| maxval = L_MAX(maxval, val5); |
| } |
| if (maxval > maskval) |
| SET_DATA_BYTE(lines, j, maxval); |
| val = GET_DATA_BYTE(lines, j); |
| |
| /* |
| * If there exists a point (q) which belongs to J(p) |
| * neighbors in anti-raster order such that J(q) < J(p) |
| * and J(p) > I(q) then |
| * fifo_add(p) */ |
| if (i < imax) { |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| if ((val7 < val) && |
| (val > GET_DATA_BYTE(linem + wplm, j))) { |
| boolval = TRUE; |
| } |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| if (!boolval && (val5 < val) && |
| (val > GET_DATA_BYTE(linem, j + 1))) { |
| boolval = TRUE; |
| } |
| } |
| if (boolval) { |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i; |
| pixel->y = j; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| } |
| } |
| |
| /* Propagation step: |
| * while fifo_empty = false |
| * p <- fifo_first() |
| * for every pixel (q) belong to neighbors of (p) |
| * if J(q) < J(p) and J(p) > I(q) |
| * J(q) <- min(J(p), I(q)); |
| * fifo_add(q); |
| * end |
| * end |
| * end */ |
| queue_size = lqueueGetCount(lq_pixel); |
| while (queue_size) { |
| pixel = (L_PIXEL *)lqueueRemove(lq_pixel); |
| i = pixel->x; |
| j = pixel->y; |
| FREE(pixel); |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| |
| if ((val = GET_DATA_BYTE(lines, j)) > 0) { |
| if (i > 0) { |
| val2 = GET_DATA_BYTE(lines - wpls, j); |
| maskval = GET_DATA_BYTE(linem - wplm, j); |
| if (val > val2 && val > maskval) { |
| SET_DATA_BYTE(lines - wpls, j, val); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i - 1; |
| pixel->y = j; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| |
| } |
| if (j > 0) { |
| val4 = GET_DATA_BYTE(lines, j - 1); |
| maskval = GET_DATA_BYTE(linem, j - 1); |
| if (val > val4 && val > maskval) { |
| SET_DATA_BYTE(lines, j - 1, val); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i; |
| pixel->y = j - 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| if (i < imax) { |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| maskval = GET_DATA_BYTE(linem + wplm, j); |
| if (val > val7 && val > maskval) { |
| SET_DATA_BYTE(lines + wpls, j, val); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i + 1; |
| pixel->y = j; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| maskval = GET_DATA_BYTE(linem, j + 1); |
| if (val > val5 && val > maskval) { |
| SET_DATA_BYTE(lines, j + 1, val); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i; |
| pixel->y = j + 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| } |
| |
| queue_size = lqueueGetCount(lq_pixel); |
| } |
| |
| break; |
| |
| case 8: |
| /* UL --> LR scan (Raster Order) |
| * If I : mask image |
| * J : marker image |
| * Let p be the currect pixel; |
| * tmp <- max{J(p) union J(p) neighbors in raster order} |
| * if (tmp > I(p)) |
| * J(p) <- tmp |
| * end */ |
| for (i = 0; i < h; i++) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = 0; j < w; j++) { |
| if ((maskval = GET_DATA_BYTE(linem, j)) < 255) { |
| maxval = GET_DATA_BYTE(lines, j); |
| if (i > 0) { |
| if (j > 0) { |
| val1 = GET_DATA_BYTE(lines - wpls, j - 1); |
| maxval = L_MAX(maxval, val1); |
| } |
| if (j < jmax) { |
| val3 = GET_DATA_BYTE(lines - wpls, j + 1); |
| maxval = L_MAX(maxval, val3); |
| } |
| val2 = GET_DATA_BYTE(lines - wpls, j); |
| maxval = L_MAX(maxval, val2); |
| } |
| if (j > 0) { |
| val4 = GET_DATA_BYTE(lines, j - 1); |
| maxval = L_MAX(maxval, val4); |
| } |
| if (maxval > maskval) |
| SET_DATA_BYTE(lines, j, maxval); |
| } |
| } |
| } |
| |
| /* LR --> UL scan (anti-raster order) |
| * If I : mask image |
| * J : marker image |
| * Let p be the currect pixel; |
| * tmp <- max{J(p) union J(p) neighbors in anti-raster order} |
| * if (tmp > I(p)) |
| * J(p) <- tmp |
| * end */ |
| for (i = imax; i >= 0; i--) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = jmax; j >= 0; j--) { |
| boolval = FALSE; |
| if ((maskval = GET_DATA_BYTE(linem, j)) < 255) { |
| maxval = GET_DATA_BYTE(lines, j); |
| if (i < imax) { |
| if (j > 0) { |
| val6 = GET_DATA_BYTE(lines + wpls, j - 1); |
| maxval = L_MAX(maxval, val6); |
| } |
| if (j < jmax) { |
| val8 = GET_DATA_BYTE(lines + wpls, j + 1); |
| maxval = L_MAX(maxval, val8); |
| } |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| maxval = L_MAX(maxval, val7); |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| maxval = L_MAX(maxval, val5); |
| } |
| if (maxval > maskval) |
| SET_DATA_BYTE(lines, j, maxval); |
| val = GET_DATA_BYTE(lines, j); |
| |
| /* |
| * If there exists a point (q) which belongs to J(p) |
| * neighbors in anti-raster order such that J(q) < J(p) |
| * and J(p) > I(q) then |
| * fifo_add(p) */ |
| if (i < imax) { |
| if (j > 0) { |
| val6 = GET_DATA_BYTE(lines + wpls, j - 1); |
| if ((val6 < val) && |
| (val > GET_DATA_BYTE(linem + wplm, j - 1))) { |
| boolval = TRUE; |
| } |
| } |
| if (j < jmax) { |
| val8 = GET_DATA_BYTE(lines + wpls, j + 1); |
| if (!boolval && (val8 < val) && |
| (val > GET_DATA_BYTE(linem + wplm, j + 1))) { |
| boolval = TRUE; |
| } |
| } |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| if (!boolval && (val7 < val) && |
| (val > GET_DATA_BYTE(linem + wplm, j))) { |
| boolval = TRUE; |
| } |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| if (!boolval && (val5 < val) && |
| (val > GET_DATA_BYTE(linem, j + 1))) { |
| boolval = TRUE; |
| } |
| } |
| if (boolval) { |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i; |
| pixel->y = j; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| } |
| } |
| |
| /* Propagation step: |
| * while fifo_empty = false |
| * p <- fifo_first() |
| * for every pixel (q) belong to neighbors of (p) |
| * if J(q) < J(p) and J(p) > I(q) |
| * J(q) <- min(J(p), I(q)); |
| * fifo_add(q); |
| * end |
| * end |
| * end */ |
| queue_size = lqueueGetCount(lq_pixel); |
| while (queue_size) { |
| pixel = (L_PIXEL *)lqueueRemove(lq_pixel); |
| i = pixel->x; |
| j = pixel->y; |
| FREE(pixel); |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| |
| if ((val = GET_DATA_BYTE(lines, j)) > 0) { |
| if (i > 0) { |
| if (j > 0) { |
| val1 = GET_DATA_BYTE(lines - wpls, j - 1); |
| maskval = GET_DATA_BYTE(linem - wplm, j - 1); |
| if (val > val1 && val > maskval) { |
| SET_DATA_BYTE(lines - wpls, j - 1, val); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i - 1; |
| pixel->y = j - 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| if (j < jmax) { |
| val3 = GET_DATA_BYTE(lines - wpls, j + 1); |
| maskval = GET_DATA_BYTE(linem - wplm, j + 1); |
| if (val > val3 && val > maskval) { |
| SET_DATA_BYTE(lines - wpls, j + 1, val); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i - 1; |
| pixel->y = j + 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| val2 = GET_DATA_BYTE(lines - wpls, j); |
| maskval = GET_DATA_BYTE(linem - wplm, j); |
| if (val > val2 && val > maskval) { |
| SET_DATA_BYTE(lines - wpls, j, val); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i - 1; |
| pixel->y = j; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| |
| } |
| if (j > 0) { |
| val4 = GET_DATA_BYTE(lines, j - 1); |
| maskval = GET_DATA_BYTE(linem, j - 1); |
| if (val > val4 && val > maskval) { |
| SET_DATA_BYTE(lines, j - 1, val); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i; |
| pixel->y = j - 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| if (i < imax) { |
| if (j > 0) { |
| val6 = GET_DATA_BYTE(lines + wpls, j - 1); |
| maskval = GET_DATA_BYTE(linem + wplm, j - 1); |
| if (val > val6 && val > maskval) { |
| SET_DATA_BYTE(lines + wpls, j - 1, val); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i + 1; |
| pixel->y = j - 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| if (j < jmax) { |
| val8 = GET_DATA_BYTE(lines + wpls, j + 1); |
| maskval = GET_DATA_BYTE(linem + wplm, j + 1); |
| if (val > val8 && val > maskval) { |
| SET_DATA_BYTE(lines + wpls, j + 1, val); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i + 1; |
| pixel->y = j + 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| maskval = GET_DATA_BYTE(linem + wplm, j); |
| if (val > val7 && val > maskval) { |
| SET_DATA_BYTE(lines + wpls, j, val); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i + 1; |
| pixel->y = j; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| maskval = GET_DATA_BYTE(linem, j + 1); |
| if (val > val5 && val > maskval) { |
| SET_DATA_BYTE(lines, j + 1, val); |
| pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL)); |
| pixel->x = i; |
| pixel->y = j + 1; |
| lqueueAdd(lq_pixel, pixel); |
| } |
| } |
| } |
| |
| queue_size = lqueueGetCount(lq_pixel); |
| } |
| break; |
| |
| default: |
| lqueueDestroy(&lq_pixel, TRUE); |
| ERROR_VOID("connectivity must be 4 or 8", procName); |
| } |
| |
| lqueueDestroy(&lq_pixel, TRUE); |
| return; |
| } |
| |
| /*-----------------------------------------------------------------------* |
| * Vincent's Iterative Grayscale Seedfill * |
| *-----------------------------------------------------------------------*/ |
| /*! |
| * seedfillGrayLowSimple() |
| * |
| * Notes: |
| * (1) The pixels are numbered as follows: |
| * 1 2 3 |
| * 4 x 5 |
| * 6 7 8 |
| * This low-level filling operation consists of two scans, |
| * raster and anti-raster, covering the entire seed image. |
| * The caller typically iterates until the filling is |
| * complete. |
| * (2) The filling action can be visualized from the following example. |
| * Suppose the mask, which clips the fill, is a sombrero-shaped |
| * surface, where the highest point is 200 and the low pixels |
| * around the rim are 30. Beyond the rim, the mask goes up a bit. |
| * Suppose the seed, which is filled, consists of a single point |
| * of height 150, located below the max of the mask, with |
| * the rest 0. Then in the raster scan, nothing happens until |
| * the high seed point is encountered, and then this value is |
| * propagated right and down, until it hits the side of the |
| * sombrero. The seed can never exceed the mask, so it fills |
| * to the rim, going lower along the mask surface. When it |
| * passes the rim, the seed continues to fill at the rim |
| * height to the edge of the seed image. Then on the |
| * anti-raster scan, the seed fills flat inside the |
| * sombrero to the upper and left, and then out from the |
| * rim as before. The final result has a seed that is |
| * flat outside the rim, and inside it fills the sombrero |
| * but only up to 150. If the rim height varies, the |
| * filled seed outside the rim will be at the highest |
| * point on the rim, which is a saddle point on the rim. |
| */ |
| void |
| seedfillGrayLowSimple(l_uint32 *datas, |
| l_int32 w, |
| l_int32 h, |
| l_int32 wpls, |
| l_uint32 *datam, |
| l_int32 wplm, |
| l_int32 connectivity) |
| { |
| l_uint8 val2, val3, val4, val5, val7, val8; |
| l_uint8 val, maxval, maskval; |
| l_int32 i, j, imax, jmax; |
| l_uint32 *lines, *linem; |
| |
| PROCNAME("seedfillGrayLowSimple"); |
| |
| imax = h - 1; |
| jmax = w - 1; |
| |
| switch (connectivity) |
| { |
| case 4: |
| /* UL --> LR scan */ |
| for (i = 0; i < h; i++) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = 0; j < w; j++) { |
| if ((maskval = GET_DATA_BYTE(linem, j)) > 0) { |
| maxval = 0; |
| if (i > 0) |
| maxval = GET_DATA_BYTE(lines - wpls, j); |
| if (j > 0) { |
| val4 = GET_DATA_BYTE(lines, j - 1); |
| maxval = L_MAX(maxval, val4); |
| } |
| val = GET_DATA_BYTE(lines, j); |
| maxval = L_MAX(maxval, val); |
| val = L_MIN(maxval, maskval); |
| SET_DATA_BYTE(lines, j, val); |
| } |
| } |
| } |
| |
| /* LR --> UL scan */ |
| for (i = imax; i >= 0; i--) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = jmax; j >= 0; j--) { |
| if ((maskval = GET_DATA_BYTE(linem, j)) > 0) { |
| maxval = 0; |
| if (i < imax) |
| maxval = GET_DATA_BYTE(lines + wpls, j); |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| maxval = L_MAX(maxval, val5); |
| } |
| val = GET_DATA_BYTE(lines, j); |
| maxval = L_MAX(maxval, val); |
| val = L_MIN(maxval, maskval); |
| SET_DATA_BYTE(lines, j, val); |
| } |
| } |
| } |
| break; |
| |
| case 8: |
| /* UL --> LR scan */ |
| for (i = 0; i < h; i++) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = 0; j < w; j++) { |
| if ((maskval = GET_DATA_BYTE(linem, j)) > 0) { |
| maxval = 0; |
| if (i > 0) { |
| if (j > 0) |
| maxval = GET_DATA_BYTE(lines - wpls, j - 1); |
| if (j < jmax) { |
| val2 = GET_DATA_BYTE(lines - wpls, j + 1); |
| maxval = L_MAX(maxval, val2); |
| } |
| val3 = GET_DATA_BYTE(lines - wpls, j); |
| maxval = L_MAX(maxval, val3); |
| } |
| if (j > 0) { |
| val4 = GET_DATA_BYTE(lines, j - 1); |
| maxval = L_MAX(maxval, val4); |
| } |
| val = GET_DATA_BYTE(lines, j); |
| maxval = L_MAX(maxval, val); |
| val = L_MIN(maxval, maskval); |
| SET_DATA_BYTE(lines, j, val); |
| } |
| } |
| } |
| |
| /* LR --> UL scan */ |
| for (i = imax; i >= 0; i--) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = jmax; j >= 0; j--) { |
| if ((maskval = GET_DATA_BYTE(linem, j)) > 0) { |
| maxval = 0; |
| if (i < imax) { |
| if (j > 0) |
| maxval = GET_DATA_BYTE(lines + wpls, j - 1); |
| if (j < jmax) { |
| val8 = GET_DATA_BYTE(lines + wpls, j + 1); |
| maxval = L_MAX(maxval, val8); |
| } |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| maxval = L_MAX(maxval, val7); |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| maxval = L_MAX(maxval, val5); |
| } |
| val = GET_DATA_BYTE(lines, j); |
| maxval = L_MAX(maxval, val); |
| val = L_MIN(maxval, maskval); |
| SET_DATA_BYTE(lines, j, val); |
| } |
| } |
| } |
| break; |
| |
| default: |
| ERROR_VOID("connectivity must be 4 or 8", procName); |
| } |
| |
| return; |
| } |
| |
| |
| /*! |
| * seedfillGrayInvLowSimple() |
| * |
| * Notes: |
| * (1) The pixels are numbered as follows: |
| * 1 2 3 |
| * 4 x 5 |
| * 6 7 8 |
| * This low-level filling operation consists of two scans, |
| * raster and anti-raster, covering the entire seed image. |
| * The caller typically iterates until the filling is |
| * complete. |
| * (2) The "Inv" signifies the fact that in this case, filling |
| * of the seed only takes place when the seed value is |
| * greater than the mask value. The mask will act to stop |
| * the fill when it is higher than the seed level. (This is |
| * in contrast to conventional grayscale filling where the |
| * seed always fills below the mask.) |
| * (3) An example of use is a basin, described by the mask (pixm), |
| * where within the basin, the seed pix (pixs) gets filled to the |
| * height of the highest seed pixel that is above its |
| * corresponding max pixel. Filling occurs while the |
| * propagating seed pixels in pixs are larger than the |
| * corresponding mask values in pixm. |
| */ |
| void |
| seedfillGrayInvLowSimple(l_uint32 *datas, |
| l_int32 w, |
| l_int32 h, |
| l_int32 wpls, |
| l_uint32 *datam, |
| l_int32 wplm, |
| l_int32 connectivity) |
| { |
| l_uint8 val1, val2, val3, val4, val5, val6, val7, val8; |
| l_uint8 maxval, maskval; |
| l_int32 i, j, imax, jmax; |
| l_uint32 *lines, *linem; |
| |
| PROCNAME("seedfillGrayInvLowSimple"); |
| |
| imax = h - 1; |
| jmax = w - 1; |
| |
| switch (connectivity) |
| { |
| case 4: |
| /* UL --> LR scan */ |
| for (i = 0; i < h; i++) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = 0; j < w; j++) { |
| if ((maskval = GET_DATA_BYTE(linem, j)) < 255) { |
| maxval = GET_DATA_BYTE(lines, j); |
| if (i > 0) { |
| val2 = GET_DATA_BYTE(lines - wpls, j); |
| maxval = L_MAX(maxval, val2); |
| } |
| if (j > 0) { |
| val4 = GET_DATA_BYTE(lines, j - 1); |
| maxval = L_MAX(maxval, val4); |
| } |
| if (maxval > maskval) |
| SET_DATA_BYTE(lines, j, maxval); |
| } |
| } |
| } |
| |
| /* LR --> UL scan */ |
| for (i = imax; i >= 0; i--) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = jmax; j >= 0; j--) { |
| if ((maskval = GET_DATA_BYTE(linem, j)) < 255) { |
| maxval = GET_DATA_BYTE(lines, j); |
| if (i < imax) { |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| maxval = L_MAX(maxval, val7); |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| maxval = L_MAX(maxval, val5); |
| } |
| if (maxval > maskval) |
| SET_DATA_BYTE(lines, j, maxval); |
| } |
| } |
| } |
| break; |
| |
| case 8: |
| /* UL --> LR scan */ |
| for (i = 0; i < h; i++) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = 0; j < w; j++) { |
| if ((maskval = GET_DATA_BYTE(linem, j)) < 255) { |
| maxval = GET_DATA_BYTE(lines, j); |
| if (i > 0) { |
| if (j > 0) { |
| val1 = GET_DATA_BYTE(lines - wpls, j - 1); |
| maxval = L_MAX(maxval, val1); |
| } |
| if (j < jmax) { |
| val2 = GET_DATA_BYTE(lines - wpls, j + 1); |
| maxval = L_MAX(maxval, val2); |
| } |
| val3 = GET_DATA_BYTE(lines - wpls, j); |
| maxval = L_MAX(maxval, val3); |
| } |
| if (j > 0) { |
| val4 = GET_DATA_BYTE(lines, j - 1); |
| maxval = L_MAX(maxval, val4); |
| } |
| if (maxval > maskval) |
| SET_DATA_BYTE(lines, j, maxval); |
| } |
| } |
| } |
| |
| /* LR --> UL scan */ |
| for (i = imax; i >= 0; i--) { |
| lines = datas + i * wpls; |
| linem = datam + i * wplm; |
| for (j = jmax; j >= 0; j--) { |
| if ((maskval = GET_DATA_BYTE(linem, j)) < 255) { |
| maxval = GET_DATA_BYTE(lines, j); |
| if (i < imax) { |
| if (j > 0) { |
| val6 = GET_DATA_BYTE(lines + wpls, j - 1); |
| maxval = L_MAX(maxval, val6); |
| } |
| if (j < jmax) { |
| val8 = GET_DATA_BYTE(lines + wpls, j + 1); |
| maxval = L_MAX(maxval, val8); |
| } |
| val7 = GET_DATA_BYTE(lines + wpls, j); |
| maxval = L_MAX(maxval, val7); |
| } |
| if (j < jmax) { |
| val5 = GET_DATA_BYTE(lines, j + 1); |
| maxval = L_MAX(maxval, val5); |
| } |
| if (maxval > maskval) |
| SET_DATA_BYTE(lines, j, maxval); |
| } |
| } |
| } |
| break; |
| |
| default: |
| ERROR_VOID("connectivity must be 4 or 8", procName); |
| } |
| |
| return; |
| } |
| |
| |
| /*-----------------------------------------------------------------------* |
| * Vincent's Distance Function method * |
| *-----------------------------------------------------------------------*/ |
| /*! |
| * distanceFunctionLow() |
| */ |
| void |
| distanceFunctionLow(l_uint32 *datad, |
| l_int32 w, |
| l_int32 h, |
| l_int32 d, |
| l_int32 wpld, |
| l_int32 connectivity) |
| { |
| l_int32 val1, val2, val3, val4, val5, val6, val7, val8, minval, val; |
| l_int32 i, j, imax, jmax; |
| l_uint32 *lined; |
| |
| PROCNAME("distanceFunctionLow"); |
| |
| /* One raster scan followed by one anti-raster scan. |
| * This does not re-set the 1-boundary of pixels that |
| * were initialized to either 0 or maxval. */ |
| imax = h - 1; |
| jmax = w - 1; |
| switch (connectivity) |
| { |
| case 4: |
| if (d == 8) { |
| /* UL --> LR scan */ |
| for (i = 1; i < imax; i++) { |
| lined = datad + i * wpld; |
| for (j = 1; j < jmax; j++) { |
| if ((val = GET_DATA_BYTE(lined, j)) > 0) { |
| val2 = GET_DATA_BYTE(lined - wpld, j); |
| val4 = GET_DATA_BYTE(lined, j - 1); |
| minval = L_MIN(val2, val4); |
| minval = L_MIN(minval, 254); |
| SET_DATA_BYTE(lined, j, minval + 1); |
| } |
| } |
| } |
| |
| /* LR --> UL scan */ |
| for (i = imax - 1; i > 0; i--) { |
| lined = datad + i * wpld; |
| for (j = jmax - 1; j > 0; j--) { |
| if ((val = GET_DATA_BYTE(lined, j)) > 0) { |
| val7 = GET_DATA_BYTE(lined + wpld, j); |
| val5 = GET_DATA_BYTE(lined, j + 1); |
| minval = L_MIN(val5, val7); |
| minval = L_MIN(minval + 1, val); |
| SET_DATA_BYTE(lined, j, minval); |
| } |
| } |
| } |
| } |
| else { /* d == 16 */ |
| /* UL --> LR scan */ |
| for (i = 1; i < imax; i++) { |
| lined = datad + i * wpld; |
| for (j = 1; j < jmax; j++) { |
| if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) { |
| val2 = GET_DATA_TWO_BYTES(lined - wpld, j); |
| val4 = GET_DATA_TWO_BYTES(lined, j - 1); |
| minval = L_MIN(val2, val4); |
| minval = L_MIN(minval, 0xfffe); |
| SET_DATA_TWO_BYTES(lined, j, minval + 1); |
| } |
| } |
| } |
| |
| /* LR --> UL scan */ |
| for (i = imax - 1; i > 0; i--) { |
| lined = datad + i * wpld; |
| for (j = jmax - 1; j > 0; j--) { |
| if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) { |
| val7 = GET_DATA_TWO_BYTES(lined + wpld, j); |
| val5 = GET_DATA_TWO_BYTES(lined, j + 1); |
| minval = L_MIN(val5, val7); |
| minval = L_MIN(minval + 1, val); |
| SET_DATA_TWO_BYTES(lined, j, minval); |
| } |
| } |
| } |
| } |
| break; |
| |
| case 8: |
| if (d == 8) { |
| /* UL --> LR scan */ |
| for (i = 1; i < imax; i++) { |
| lined = datad + i * wpld; |
| for (j = 1; j < jmax; j++) { |
| if ((val = GET_DATA_BYTE(lined, j)) > 0) { |
| val1 = GET_DATA_BYTE(lined - wpld, j - 1); |
| val2 = GET_DATA_BYTE(lined - wpld, j); |
| val3 = GET_DATA_BYTE(lined - wpld, j + 1); |
| val4 = GET_DATA_BYTE(lined, j - 1); |
| minval = L_MIN(val1, val2); |
| minval = L_MIN(minval, val3); |
| minval = L_MIN(minval, val4); |
| minval = L_MIN(minval, 254); |
| SET_DATA_BYTE(lined, j, minval + 1); |
| } |
| } |
| } |
| |
| /* LR --> UL scan */ |
| for (i = imax - 1; i > 0; i--) { |
| lined = datad + i * wpld; |
| for (j = jmax - 1; j > 0; j--) { |
| if ((val = GET_DATA_BYTE(lined, j)) > 0) { |
| val8 = GET_DATA_BYTE(lined + wpld, j + 1); |
| val7 = GET_DATA_BYTE(lined + wpld, j); |
| val6 = GET_DATA_BYTE(lined + wpld, j - 1); |
| val5 = GET_DATA_BYTE(lined, j + 1); |
| minval = L_MIN(val8, val7); |
| minval = L_MIN(minval, val6); |
| minval = L_MIN(minval, val5); |
| minval = L_MIN(minval + 1, val); |
| SET_DATA_BYTE(lined, j, minval); |
| } |
| } |
| } |
| } |
| else { /* d == 16 */ |
| /* UL --> LR scan */ |
| for (i = 1; i < imax; i++) { |
| lined = datad + i * wpld; |
| for (j = 1; j < jmax; j++) { |
| if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) { |
| val1 = GET_DATA_TWO_BYTES(lined - wpld, j - 1); |
| val2 = GET_DATA_TWO_BYTES(lined - wpld, j); |
| val3 = GET_DATA_TWO_BYTES(lined - wpld, j + 1); |
| val4 = GET_DATA_TWO_BYTES(lined, j - 1); |
| minval = L_MIN(val1, val2); |
| minval = L_MIN(minval, val3); |
| minval = L_MIN(minval, val4); |
| minval = L_MIN(minval, 0xfffe); |
| SET_DATA_TWO_BYTES(lined, j, minval + 1); |
| } |
| } |
| } |
| |
| /* LR --> UL scan */ |
| for (i = imax - 1; i > 0; i--) { |
| lined = datad + i * wpld; |
| for (j = jmax - 1; j > 0; j--) { |
| if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) { |
| val8 = GET_DATA_TWO_BYTES(lined + wpld, j + 1); |
| val7 = GET_DATA_TWO_BYTES(lined + wpld, j); |
| val6 = GET_DATA_TWO_BYTES(lined + wpld, j - 1); |
| val5 = GET_DATA_TWO_BYTES(lined, j + 1); |
| minval = L_MIN(val8, val7); |
| minval = L_MIN(minval, val6); |
| minval = L_MIN(minval, val5); |
| minval = L_MIN(minval + 1, val); |
| SET_DATA_TWO_BYTES(lined, j, minval); |
| } |
| } |
| } |
| } |
| break; |
| |
| default: |
| ERROR_VOID("connectivity must be 4 or 8", procName); |
| break; |
| } |
| |
| return; |
| } |
| |
| |
| /*-----------------------------------------------------------------------* |
| * Seed spread (based on distance function) * |
| *-----------------------------------------------------------------------*/ |
| /*! |
| * seedspreadLow() |
| * |
| * See pixSeedspread() for a brief description of the algorithm here. |
| */ |
| void |
| seedspreadLow(l_uint32 *datad, |
| l_int32 w, |
| l_int32 h, |
| l_int32 wpld, |
| l_uint32 *datat, |
| l_int32 wplt, |
| l_int32 connectivity) |
| { |
| l_int32 val1t, val2t, val3t, val4t, val5t, val6t, val7t, val8t; |
| l_int32 i, j, imax, jmax, minval, valt, vald; |
| l_uint32 *linet, *lined; |
| |
| PROCNAME("seedspreadLow"); |
| |
| /* One raster scan followed by one anti-raster scan. |
| * pixt is initialized to have 0 on pixels where the |
| * input is specified in pixd, and to have 1 on all |
| * other pixels. We only change pixels in pixt and pixd |
| * that are non-zero in pixt. */ |
| imax = h - 1; |
| jmax = w - 1; |
| switch (connectivity) |
| { |
| case 4: |
| /* UL --> LR scan */ |
| for (i = 1; i < h; i++) { |
| linet = datat + i * wplt; |
| lined = datad + i * wpld; |
| for (j = 1; j < jmax; j++) { |
| if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) { |
| val2t = GET_DATA_TWO_BYTES(linet - wplt, j); |
| val4t = GET_DATA_TWO_BYTES(linet, j - 1); |
| minval = L_MIN(val2t, val4t); |
| minval = L_MIN(minval, 0xfffe); |
| SET_DATA_TWO_BYTES(linet, j, minval + 1); |
| if (val2t < val4t) |
| vald = GET_DATA_BYTE(lined - wpld, j); |
| else |
| vald = GET_DATA_BYTE(lined, j - 1); |
| SET_DATA_BYTE(lined, j, vald); |
| } |
| } |
| } |
| |
| /* LR --> UL scan */ |
| for (i = imax - 1; i > 0; i--) { |
| linet = datat + i * wplt; |
| lined = datad + i * wpld; |
| for (j = jmax - 1; j > 0; j--) { |
| if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) { |
| val7t = GET_DATA_TWO_BYTES(linet + wplt, j); |
| val5t = GET_DATA_TWO_BYTES(linet, j + 1); |
| minval = L_MIN(val5t, val7t); |
| minval = L_MIN(minval + 1, valt); |
| if (valt > minval) { /* replace */ |
| SET_DATA_TWO_BYTES(linet, j, minval); |
| if (val5t < val7t) |
| vald = GET_DATA_BYTE(lined, j + 1); |
| else |
| vald = GET_DATA_BYTE(lined + wplt, j); |
| SET_DATA_BYTE(lined, j, vald); |
| } |
| } |
| } |
| } |
| break; |
| case 8: |
| /* UL --> LR scan */ |
| for (i = 1; i < h; i++) { |
| linet = datat + i * wplt; |
| lined = datad + i * wpld; |
| for (j = 1; j < jmax; j++) { |
| if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) { |
| val1t = GET_DATA_TWO_BYTES(linet - wplt, j - 1); |
| val2t = GET_DATA_TWO_BYTES(linet - wplt, j); |
| val3t = GET_DATA_TWO_BYTES(linet - wplt, j + 1); |
| val4t = GET_DATA_TWO_BYTES(linet, j - 1); |
| minval = L_MIN(val1t, val2t); |
| minval = L_MIN(minval, val3t); |
| minval = L_MIN(minval, val4t); |
| minval = L_MIN(minval, 0xfffe); |
| SET_DATA_TWO_BYTES(linet, j, minval + 1); |
| if (minval == val1t) |
| vald = GET_DATA_BYTE(lined - wpld, j - 1); |
| else if (minval == val2t) |
| vald = GET_DATA_BYTE(lined - wpld, j); |
| else if (minval == val3t) |
| vald = GET_DATA_BYTE(lined - wpld, j + 1); |
| else /* minval == val4t */ |
| vald = GET_DATA_BYTE(lined, j - 1); |
| SET_DATA_BYTE(lined, j, vald); |
| } |
| } |
| } |
| |
| /* LR --> UL scan */ |
| for (i = imax - 1; i > 0; i--) { |
| linet = datat + i * wplt; |
| lined = datad + i * wpld; |
| for (j = jmax - 1; j > 0; j--) { |
| if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) { |
| val8t = GET_DATA_TWO_BYTES(linet + wplt, j + 1); |
| val7t = GET_DATA_TWO_BYTES(linet + wplt, j); |
| val6t = GET_DATA_TWO_BYTES(linet + wplt, j - 1); |
| val5t = GET_DATA_TWO_BYTES(linet, j + 1); |
| minval = L_MIN(val8t, val7t); |
| minval = L_MIN(minval, val6t); |
| minval = L_MIN(minval, val5t); |
| minval = L_MIN(minval + 1, valt); |
| if (valt > minval) { /* replace */ |
| SET_DATA_TWO_BYTES(linet, j, minval); |
| if (minval == val5t + 1) |
| vald = GET_DATA_BYTE(lined, j + 1); |
| else if (minval == val6t + 1) |
| vald = GET_DATA_BYTE(lined + wpld, j - 1); |
| else if (minval == val7t + 1) |
| vald = GET_DATA_BYTE(lined + wpld, j); |
| else /* minval == val8t + 1 */ |
| vald = GET_DATA_BYTE(lined + wpld, j + 1); |
| SET_DATA_BYTE(lined, j, vald); |
| } |
| } |
| } |
| } |
| break; |
| default: |
| ERROR_VOID("connectivity must be 4 or 8", procName); |
| break; |
| } |
| |
| return; |
| } |
