Thread Subject: parallelogram mask

I would like to use a parallelogram mask for every pixel on the image and to calculate the median value within the parallelogram mask. Can anyone help me to define a parallelogram mask?

Thanks to all in advance!

"Amy Wang" <amy.wang@ua.ac.be> wrote in message <gorde9$af8$1@fred.mathworks.com>...
> I would like to use a parallelogram mask for every pixel on the image and to calculate the median value within the parallelogram mask. Can anyone help me to define a parallelogram mask?
>
> Thanks to all in advance!

It's not clear what you mean by "use a parallelogram mask for a pixel"

"Amy Wang" <amy.wang@ua.ac.be> wrote in message <gorde9$af8$1@fred.mathworks.com>...
> I would like to use a parallelogram mask for every pixel on the image and to calculate the median value within the parallelogram mask. Can anyone help me to define a parallelogram mask?
>
> Thanks to all in advance!

  I assume you want the parallelogram centered over each pixel position. Such a parallelogram can be defined in terms of two unit vectors u = [u1,u2] and v = [v1,v2] (satisfying u1^2+u2^2=1 and v1^2+v2^2=1) which are parallel to two adjacent sides of the parallelogram, and two orthogonal distances, g and h, of the center from these respective sides. Then if (x0,y0) is a particular pixel position, any point (x,y) will lie inside the parallelogram mask centered on (x0,y0) if and only if the following two inequalities are both satisfied:

 abs(u2*(x-x0)-u1*(y-y0)) <= g
 abs(v2*(x-x0)-v1*(y-y0)) <= h

  That is the geometric side of the problem. As for calculating a median value, I am not an expert in filter theory but I suspect the matlab 'filter' function will not serve your purposes here. You will probably have to apply the above inequalities to 'meshgrid' indices for each different pixel and convert these to single indexes using 'sub2ind'. The 'median' function can then be applied to arrays of image values at these single-index points. Each such array would have as many elements as lie inside the particular parallelogram. It sounds like a time-consuming computation.

Roger Stafford

"Amy Wang" <amy.wang@ua.ac.be> wrote in message <gorde9$af8$1@fred.mathworks.com>...
> I would like to use a parallelogram mask for every pixel on the image and to calculate the median value within the parallelogram mask.
> ........

  It has occurred to me that if each of your parallelograms has a fairly large number of pixels within it, there exists a method of avoiding the numerous and therefore time-consuming calls on matlab's 'median' function in your problem. Each call on 'median' requires a sorting or sorting-like action in locating the position of the median value and this makes the algorithm of a higher order (n*log(n)) than that of simply finding a mean value, which is only of order n. This seems a shame when we could do a one-time sort of the entire image and then have no further need for any sorting.

  Suppose first that in the beginning you do a one-time sort of the original array of pixel values, x(:), as follows:

 [y,p] = sort(x(:));

These vectors, y and p, can then be used to aid in calculating each of the medians you desire without requiring a further sort action.

  For each pixel suppose 't' is the logical result of applying the inequalities I discussed earlier corresponding to that pixel, with "trues" indicating those pixels lying within the surrounding parallelogram. Then to find the median, m, of these parallelogram pixel values, rather than calling on median(x(t)), you can do this:

 a = y(t(p)); % Get parallelogram pixel values in ascending order
 n = numel(a); % The number of pixels in parallelogram
 m = (a(ceil(n/2))+a(ceil((n+1)/2)))/2; % Fast median

which involves no sorting. The array 'a' here consists of the parallelogram pixel values from x(t) but in ascending order by virtue of the permutation 'p'. Hence no actual sorting need take place to find the median.

  It should be pointed out that the above is a saving in computer time only if the number n is large enough to make a median call more time-consuming than the processing involved in evaluating the expression t(p), which does involve the entire image until being reduced to array 'a' of size n by the logical indexing.

  Note: I was wrong earlier when I stated you would need to use 'sub2ind'. All you need to do is use logical indexing to obtain a list of the parallelogram pixel values. However, if they are unsorted, a call to 'median' would be necessary.

Roger Stafford

Thanks for the advices!
Saved me lots of computing time :)

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gotb6j$bbp$1@fred.mathworks.com>...
> "Amy Wang" <amy.wang@ua.ac.be> wrote in message <gorde9$af8$1@fred.mathworks.com>...
> > I would like to use a parallelogram mask for every pixel on the image and to calculate the median value within the parallelogram mask.
> > ........
>
> It has occurred to me that if each of your parallelograms has a fairly large number of pixels within it, there exists a method of avoiding the numerous and therefore time-consuming calls on matlab's 'median' function in your problem. Each call on 'median' requires a sorting or sorting-like action in locating the position of the median value and this makes the algorithm of a higher order (n*log(n)) than that of simply finding a mean value, which is only of order n. This seems a shame when we could do a one-time sort of the entire image and then have no further need for any sorting.
>
> Suppose first that in the beginning you do a one-time sort of the original array of pixel values, x(:), as follows:
>
> [y,p] = sort(x(:));
>
> These vectors, y and p, can then be used to aid in calculating each of the medians you desire without requiring a further sort action.
>
> For each pixel suppose 't' is the logical result of applying the inequalities I discussed earlier corresponding to that pixel, with "trues" indicating those pixels lying within the surrounding parallelogram. Then to find the median, m, of these parallelogram pixel values, rather than calling on median(x(t)), you can do this:
>
> a = y(t(p)); % Get parallelogram pixel values in ascending order
> n = numel(a); % The number of pixels in parallelogram
> m = (a(ceil(n/2))+a(ceil((n+1)/2)))/2; % Fast median
>
> which involves no sorting. The array 'a' here consists of the parallelogram pixel values from x(t) but in ascending order by virtue of the permutation 'p'. Hence no actual sorting need take place to find the median.
>
> It should be pointed out that the above is a saving in computer time only if the number n is large enough to make a median call more time-consuming than the processing involved in evaluating the expression t(p), which does involve the entire image until being reduced to array 'a' of size n by the logical indexing.
>
> Note: I was wrong earlier when I stated you would need to use 'sub2ind'. All you need to do is use logical indexing to obtain a list of the parallelogram pixel values. However, if they are unsorted, a call to 'median' would be necessary.
>
> Roger Stafford