Thread Subject: Presence of logical ones around a pixel in a certain direction and distance

Hi there,

Lets say I have binary image. Given a pixel I want to find
the number of non-zero values around it in a certain radius,
in a certain direction. Lets say I have divided the region
around the pixel into 30deg regions (starting from north,
0-30 deg, 30-60deg ... 330-360 deg) upto a distance of x
pixels, so that it makes a radial region around the pixel
concerned, with spokes at every 30 degrees. I want to find
all logical 1 pixels in each region. What would be the
fastest way to perform this?

Eventually I want to do binning of the number of non-zero
values around a certain pixel. (According to my example
there will be 360/30 = 12 bins). Looking for an extremely
fast way...since I'll be doing this for many pixels


Regards,

"Ahmad " <ahmad.humyn@gmail.com> wrote in message
<g09hms$lev$1@fred.mathworks.com>...
> Hi there,
>
> Lets say I have binary image. Given a pixel I want to find
> the number of non-zero values around it in a certain
radius,
> in a certain direction. Lets say I have divided the region
> around the pixel into 30deg regions (starting from north,
> 0-30 deg, 30-60deg ... 330-360 deg) upto a distance of x
> pixels, so that it makes a radial region around the pixel
> concerned, with spokes at every 30 degrees. I want to find
> all logical 1 pixels in each region. What would be the
> fastest way to perform this?
>
> Eventually I want to do binning of the number of non-zero
> values around a certain pixel. (According to my example
> there will be 360/30 = 12 bins). Looking for an extremely
> fast way...since I'll be doing this for many pixels
>
>
> Regards,

Until someone comes up with a better way, here's one.

First, you can initially compute the rows and columns of
each non-zero point:

[i j] = find(A);


Then, for each point p where p = [row col] that you want to
perform your histogram and for a maximum distance of
maxDist, use:

p = [20 33];
maxDist = 12;

closePts = hypot(p(1)-i,p(2)-j)<=maxDist;
allAngles = mod(ceil(atan2(p(2)-j(closePts),...
  p(1)-i(closePts))/pi*6),12)+1;
nPer = hist(allAngles,1:12);


where nPer is 1-by-12 and the first element is # of
nonzeros in the range [0 30) deg, second from [30 60), etc.

I can see a few improvements you can make for performance
depending on your application. One might be to use:

closePts = (p(1)-i).'*(p(2)-j))<=maxDist^2;

Good luck

Thanks a lot :)

These tips look extremely helpful. Please do tell, if you
find a faster way :)

Regards,

"helper " <spamless@nospam.com> wrote in message
<g09ont$rtu$1@fred.mathworks.com>...
> "Ahmad " <ahmad.humyn@gmail.com> wrote in message
> <g09hms$lev$1@fred.mathworks.com>...
> > Hi there,
> >
> > Lets say I have binary image. Given a pixel I want to find
> > the number of non-zero values around it in a certain
> radius,
> > in a certain direction. Lets say I have divided the region
> > around the pixel into 30deg regions (starting from north,
> > 0-30 deg, 30-60deg ... 330-360 deg) upto a distance of x
> > pixels, so that it makes a radial region around the pixel
> > concerned, with spokes at every 30 degrees. I want to find
> > all logical 1 pixels in each region. What would be the
> > fastest way to perform this?
> >
> > Eventually I want to do binning of the number of non-zero
> > values around a certain pixel. (According to my example
> > there will be 360/30 = 12 bins). Looking for an extremely
> > fast way...since I'll be doing this for many pixels
> >
> >
> > Regards,
>
> Until someone comes up with a better way, here's one.
>
> First, you can initially compute the rows and columns of
> each non-zero point:
>
> [i j] = find(A);
>
>
> Then, for each point p where p = [row col] that you want to
> perform your histogram and for a maximum distance of
> maxDist, use:
>
> p = [20 33];
> maxDist = 12;
>
> closePts = hypot(p(1)-i,p(2)-j)<=maxDist;
> allAngles = mod(ceil(atan2(p(2)-j(closePts),...
> p(1)-i(closePts))/pi*6),12)+1;
> nPer = hist(allAngles,1:12);
>
>
> where nPer is 1-by-12 and the first element is # of
> nonzeros in the range [0 30) deg, second from [30 60), etc.
>
> I can see a few improvements you can make for performance
> depending on your application. One might be to use:
>
> closePts = (p(1)-i).'*(p(2)-j))<=maxDist^2;
>
> Good luck

In article <g09ont$rtu$1@fred.mathworks.com>,
helper <spamless@nospam.com> wrote:
>"Ahmad " <ahmad.humyn@gmail.com> wrote in message
><g09hms$lev$1@fred.mathworks.com>...

>> Lets say I have binary image. Given a pixel I want to find
>> the number of non-zero values around it in a certain
>radius,
>> in a certain direction. Lets say I have divided the region
>> around the pixel into 30deg regions (starting from north,
>> 0-30 deg, 30-60deg ... 330-360 deg) upto a distance of x
>> pixels, so that it makes a radial region around the pixel
>> concerned, with spokes at every 30 degrees. I want to find
>> all logical 1 pixels in each region.

>> Looking for an extremely
>> fast way...since I'll be doing this for many pixels

>Until someone comes up with a better way, here's one.


>I can see a few improvements you can make for performance
>depending on your application. One might be to use:

>closePts = (p(1)-i).'*(p(2)-j))<=maxDist^2;

If the radius stays the same for each pixel, then for a given
angular sector, the relative offsets of the pixels to be examined
will be the same for each pixel to be examined. One could therefor
pre-calculate the relative offsets for each of the angular sectors,
and then as one stepped through the various pixels, it would become
a straightforward "add absolute index of current pixel to
relative indices and access the array at those locations" and process
the resulting vector.
--
  "After all, what problems has intellectualism ever solved?"
                                              -- Robert Gilman

> If the radius stays the same for each pixel, then for a
given
> angular sector, the relative offsets of the pixels to be
examined
> will be the same for each pixel to be examined. One could
therefor
> pre-calculate the relative offsets for each of the
angular sectors,
> and then as one stepped through the various pixels, it
would become
> a straightforward "add absolute index of current pixel to
> relative indices and access the array at those locations"
and process
> the resulting vector.

That would be true for the angles as well, and is the
method I initially considered. However the problem occurs
when you specify a point near the edge of the matrix.
Handling this case might negate any performance gains you
get by precomputing any "mask".

On May 12, 9:46=A0am, "Ahmad " <ahmad.hu...@gmail.com> wrote:
> Hi there,
>
> Lets say I have binary image. Given a pixel I want to find
> the number of non-zero values around it in a certain radius,
> in a certain direction. Lets say I have divided the region
> around the pixel into 30deg regions (starting from north,
> 0-30 deg, 30-60deg ... 330-360 deg) upto a distance of x
> pixels, so that it makes a radial region around the pixel
> concerned, with spokes at every 30 degrees. I want to find
> all logical 1 pixels in each region. What would be the
> fastest way to perform this?
>
> Eventually I want to do binning of the number of non-zero
> values around a certain pixel. (According to my example
> there will be 360/30 =3D 12 bins). Looking for an extremely
> fast way...since I'll be doing this for many pixels
>
> Regards,

--------------------------------------------------
Ahmad:
Simple - I'd just do 12 convolutions. Make up a convolution kernel,
well 12 of them actually with 1's placed in the sector you want to
look at and 0's in the other sectors. Then simply call the conv2
function once for each kernel. The pixel value in the resulting 12
images will tell you how many pixels were in the sector (pie-slice
shape) centered on that pixel for that particular sector orientation.
Look up the documentation for the convolution filter and you'll see
why it does exactly what you asked for. It's in the image processing
toolbox, but I think there's a version of it in base MATLAB.

As far as timing, you would just have to try it versus the other
methods suggested. You could probably do all 12 for ordinary sized
images in just a second or two, in which case the time is probably not
all that much of a concern. How big are your images? How many do you
have to process (hundreds or thousands)? That is, don't knock
yourself out trying to shave the time down from 0.53 seconds to 0.37
seconds - your users will never notice. Today I read in and processed
in about 2 minutes a single 3D image that was 1.2 GB in size (yes
gigabytes, so no wonder I laugh when I see people talk about a "large"
array that is a few hundred thousand elements). I remember years ago
when we had images of 512x512 (256 KB), we thought a minute or so per
image was reasonable. How times have changed.
Regards,
ImageAnalyst