do you know an application to simple edge detection for image blocks?

Hi all,

I guess I "invented" an algorithm to detect if an diagonal edge exists in a
8x8 block or not...

The algorithm is to answer YES or NO to the question that if a block has
diagonal edges...  It can only answer YES and NO, it will not label the edge
pixels...

My algorithm is simpler than using edge detector--taking gradient, etc.
since those techniques involve large number of computations.

I am not sure how important my idea is --- so far I did not see any
application that needs to ask YES/NO if a diagonal edge exists in a block.

Do you know or have been aware of any applications that may utilize my idea?

Thanks and regards,

-Jeonyim

Hello Joenyim Kim,
Some demosaicing algos use edge detection to guide their interpolation.You
could look into these to see if what you have can be useful here.
-- 
Clay S. Turner, V.P.
Wireless Systems Engineering, Inc.
Satellite Beach, Florida 32937
(321) 777-7889
www.wse.biz
csturner@wse.biz



"Joenyim Kim" <jeonyimkim80@yahoo.com> wrote in message
news:bv8pkf$9t4$1@mozo.cc.purdue.edu...
> Hi all,
>
> I guess I "invented" an algorithm to detect if an diagonal edge exists in
a
> 8x8 block or not...
>
> The algorithm is to answer YES or NO to the question that if a block has
> diagonal edges...  It can only answer YES and NO, it will not label the
edge
> pixels...
>
> My algorithm is simpler than using edge detector--taking gradient, etc.
> since those techniques involve large number of computations.
>
> I am not sure how important my idea is --- so far I did not see any
> application that needs to ask YES/NO if a diagonal edge exists in a block.
>
> Do you know or have been aware of any applications that may utilize my
idea?
>
> Thanks and regards,
>
> -Jeonyim
>
>
>
>

Being one person who worked on demosaicing algorithms for demosaicing CMOS
image sensors, I can confirm that we needed *very fast* edge detection
algorithms. However, the edge detection was tied into the demosaicing
itself--that is, the decision of which (e.g.) R bayer pixels to use to
create R for a G, was based on an algorithm that included the detection of
whether the G was placed at an edge in R.

(most CMOS sensors are dyed with a "bayer pattern", that is: R1G1R1G1R1G1

G2B1G2B1G2B1

R1G1R1G1R1G1
and "demosaicing" means trying to recover R,G,B for every single pixel. Also
note that the normal notation is R,G,B,g, where G and g are the two (usually
different) green dyes, but I used numbers to keep the colors in all caps, so
that spacing due to small case g wasn't a problem.)

Joenyim--I would give details on the edge detection algorithm I used, but it
may belong to my previous employer (I'd have to check), and you did not
describe yours.

Also, in exploring "fast" algorithms that may be extremely computationally
efficient by not "optimal", you are in "engineering-space", rather than
"academia-space". You could really patent it if it were much faster than the
currently accepted "optimal" algorithm, and also "optimal". However, when it
is sub-optimal, it moves into the engineering cost/benefit space. That is, I
came up with many, many, cool ways to do demosaicing (including edge cases),
but the one we ended up usinig was the one that had the "best"
results/computation-time (given the processor we were using, which we would
not change) tradeoff, according the marketing and the customers. It was not
the fastest, and it was not the most performant.

Jim

"Clay S. Turner" <CSTurner@WSE.Biz> wrote in message
news:7tSRb.26035$L04.9227@bignews4.bellsouth.net...
> Hello Joenyim Kim,
> Some demosaicing algos use edge detection to guide their interpolation.You
> could look into these to see if what you have can be useful here.
> --
> Clay S. Turner, V.P.
> Wireless Systems Engineering, Inc.
> Satellite Beach, Florida 32937
> (321) 777-7889
> www.wse.biz
> csturner@wse.biz
>
>
>
> "Joenyim Kim" <jeonyimkim80@yahoo.com> wrote in message
> news:bv8pkf$9t4$1@mozo.cc.purdue.edu...
> > Hi all,
> >
> > I guess I "invented" an algorithm to detect if an diagonal edge exists
in
> a
> > 8x8 block or not...
> >
> > The algorithm is to answer YES or NO to the question that if a block has
> > diagonal edges...  It can only answer YES and NO, it will not label the
> edge
> > pixels...
> >
> > My algorithm is simpler than using edge detector--taking gradient, etc.
> > since those techniques involve large number of computations.
> >
> > I am not sure how important my idea is --- so far I did not see any
> > application that needs to ask YES/NO if a diagonal edge exists in a
block.
> >
> > Do you know or have been aware of any applications that may utilize my
> idea?
> >
> > Thanks and regards,
> >
> > -Jeonyim
> >
> >
> >
> >
>
>

"Joenyim Kim" <jeonyimkim80@yahoo.com> wrote in message news:<bv8pkf$9t4$1@mozo.cc.purdue.edu>...
> Hi all,
> 
> I guess I "invented" an algorithm to detect if an diagonal edge exists in a
> 8x8 block or not...
> 
> The algorithm is to answer YES or NO to the question that if a block has
> diagonal edges...  It can only answer YES and NO, it will not label the edge
> pixels...
> 
> My algorithm is simpler than using edge detector--taking gradient, etc.
> since those techniques involve large number of computations.
> 
> I am not sure how important my idea is --- so far I did not see any
> application that needs to ask YES/NO if a diagonal edge exists in a block.
> 
> Do you know or have been aware of any applications that may utilize my idea?
> 
> Thanks and regards,
> 
> -Jeonyim

We're developing a computer vision algorithm to locate a specific
symbol in an image.  The symbol is a circled white X on a black
background, and its position, scale, and 3D orientation are unknown in
the frame of the photograph.  A couple of conventional methods that
we've considered using to locate the symbol are the Hough transform
and template matching.

If you're not keen on leaking the algorithm, just post the semantics. 
For example, what do you define as "diagonal"?  How well does it deal
with noise?  How fast is it compared to similar approaches... can you
give test results?  Can it find thick lines?  Etc.  I'd definitely be
interested in hearing.  Although edge detection is probably the most
researched subject in image processing, I'm not willing to concede
that the best algorithms have already been published.

-- Brian Stone

"Jim Gort" <jgort@comcast.net> wrote in message
news:cseSb.181343$xy6.869685@attbi_s02...
> Being one person who worked on demosaicing algorithms for demosaicing CMOS
> image sensors, I can confirm that we needed *very fast* edge detection
> algorithms. However, the edge detection was tied into the demosaicing
> itself--that is, the decision of which (e.g.) R bayer pixels to use to
> create R for a G, was based on an algorithm that included the detection of
> whether the G was placed at an edge in R.

Hi, Jim, thank you for the information! I did not know CMOS sensor before
you pointed me to. Ha, it is better than CCD, and can do a lot things.
Interesting.

>
> (most CMOS sensors are dyed with a "bayer pattern", that is: R1G1R1G1R1G1
>
> G2B1G2B1G2B1
>
> R1G1R1G1R1G1
> and "demosaicing" means trying to recover R,G,B for every single pixel.
Also
> note that the normal notation is R,G,B,g, where G and g are the two
(usually
> different) green dyes, but I used numbers to keep the colors in all caps,
so
> that spacing due to small case g wasn't a problem.)
>

so you do edge-detection even when you don't have pixels quite ready yet...
that's to say, you use edge-detection to help interpolate some missing
pixels?

in that case my algorithm might not be able to help: it needs some side
information when all pixels are ready... but I will think about it to
improve and see if I can use some side information ready inside the CMOS
sensor at the demosaicing time.

but on the other hand, knowing that a CMOS sensor can be edge-detection
itself lend me to some other ideas to utilize the functionality of CMOS
sensor. Would you mind telling me how does edge-detection relate to the
interpolation of missing pixels in CMOS sensor? Is that only YES/NO answer
that is needed? I guess the edge-detection should not only fast but also as
simple as possible for energy concern?

> Also, in exploring "fast" algorithms that may be extremely computationally
> efficient by not "optimal", you are in "engineering-space", rather than
> "academia-space". You could really patent it if it were much faster than
the
> currently accepted "optimal" algorithm, and also "optimal". However, when
it
> is sub-optimal, it moves into the engineering cost/benefit space. That is,
I
> came up with many, many, cool ways to do demosaicing (including edge
cases),
> but the one we ended up usinig was the one that had the "best"
> results/computation-time (given the processor we were using, which we
would
> not change) tradeoff, according the marketing and the customers. It was
not
> the fastest, and it was not the most performant.
>

I guess inventing a new algorithm(hopefully I am the first, I am not sure
myself, also I am not sure if it is useful at all...:=) is "academia-space",
tweak existing algorithms for tradeoffs is "engineering-space"... :=)

Regards,

-Jeonyim

"Brian Stone" <no.more.spam@stoneentertainment.com> wrote in message
news:acd67ea1.0401291748.7419c4fc@posting.google.com...
> "Joenyim Kim" <jeonyimkim80@yahoo.com> wrote in message
news:<bv8pkf$9t4$1@mozo.cc.purdue.edu>...

Hi Brian,

Thank you for your information!
>
> We're developing a computer vision algorithm to locate a specific
> symbol in an image.  The symbol is a circled white X on a black
> background, and its position, scale, and 3D orientation are unknown in
> the frame of the photograph.

This is like targeting and shooting... heh heh :=)

> A couple of conventional methods that
> we've considered using to locate the symbol are the Hough transform
> and template matching.

What's the relationship between the circled white X with edge detection?

> If you're not keen on leaking the algorithm, just post the semantics.
> For example, what do you define as "diagonal"?

I mean almost 45 degree slope lines.

> How well does it deal with noise?

I am not sure. Your application is like you need to distinguish a circled
cross from its background. The background itself can be an image. So what if
the image itself has diagonal edges? My algorithm can not distinguish that
crossed edge from the edges in image itself...

> How fast is it compared to similar approaches... can you
> give test results?

Should be very very fast; and it likes to work on large images.

>Can it find thick lines?

I am going to test this... It is an interesting problem. I have not thought
it before... :=)

>  I'd definitely be
> interested in hearing.  Although edge detection is probably the most
> researched subject in image processing, I'm not willing to concede
> that the best algorithms have already been published.

Once again, the scope of my algorithm is to find YES/NO answer to the
question whether an diagonal edge exists or not. It might also work for a
cross... But it does this in a blockbased method. The speed improvement
comes from the fact that it just seeks for binary answer.

Best regards,

-Jeonyim

Joenyim:

I guess I didn't explain the bayer pattern very well. Let me try again.

The CMOS arrays I have worked with (and I think most used for consumer
cameras, etc.) are dyed with a pattern of colors. That is, any given pixel
in the array is dyed with either R, G, or B. Thus, it is responsive to
(mostly) only that color. Every 2x2 block of pixels has one dyed with R, one
with B, and two with G (actually, two different green dyes are usually used,
but for simplicity and proper spacing:
RGRGRG
GBGBGB
RGRGRG
GBGBGB
etc.
Thus, the resolution of R and B is 1/4 that of the sensor, and in G its 1/2
(G is given twice the resoltion of R, as it his the highest luminance
content--similar to YCrCb--Y is usually given twice the resolution as Cr and
Cb).

However, for most applications, this bayer pattern must be processed to
create R,G,B for every single pixel. That is, a pixel that is dyed R must
also be given a G and B. The question is, how to derive the G and B from the
neighbors that are actually dyed G and B.

A simplistic way would be to average the 4 nearest Bs, and the 4 nearest Gs
(linear interpolation). However, what if the R pixel lies on an edge in B?
The simplistic way would create unwanted artifacts in B along the edge
(consider, in the above, if the first row of B are all solid blue and the
second row has no blue--what would the blue recovered for GBGBGB pixels in
the row in between look like?). Thus, edge detection is used to guide the
interpolation algorithm to prevent this--needed is not only yes/no, but also
directional information.

I think this is one case of the general problem of interpolation. However,
since this must be done very very quickly to keep cost of processing power
down (e.g., in a digital camera), the literature on great interpolation
methods is mostly unusable, and ad-hoc methods prevail.

Also, I thought of another application I've worked on where fast ad-hoc edge
detection methods were used, due to limited processing power--inspection
systems to verify line width, etc. in PCBs and silicon wafers...... This
application may be better suited to a fast yes/no algorithm.

I disagree with your last statement. The task of the engineer is to
understand and utilize whatever tools/methods are available and applicable,
but invent his/her own to get the job done when none are. ALL of the great
inventors of our time were engineers (IMHO)

Jim

"Joenyim Kim" <jeonyimkim80@yahoo.com> wrote in message
news:bvjmgv$bdl$1@mozo.cc.purdue.edu...
>
> "Jim Gort" <jgort@comcast.net> wrote in message
> news:cseSb.181343$xy6.869685@attbi_s02...
> > Being one person who worked on demosaicing algorithms for demosaicing
CMOS
> > image sensors, I can confirm that we needed *very fast* edge detection
> > algorithms. However, the edge detection was tied into the demosaicing
> > itself--that is, the decision of which (e.g.) R bayer pixels to use to
> > create R for a G, was based on an algorithm that included the detection
of
> > whether the G was placed at an edge in R.
>
> Hi, Jim, thank you for the information! I did not know CMOS sensor before
> you pointed me to. Ha, it is better than CCD, and can do a lot things.
> Interesting.
>
> >
> > (most CMOS sensors are dyed with a "bayer pattern", that is:
R1G1R1G1R1G1
> >
> > G2B1G2B1G2B1
> >
> > R1G1R1G1R1G1
> > and "demosaicing" means trying to recover R,G,B for every single pixel.
> Also
> > note that the normal notation is R,G,B,g, where G and g are the two
> (usually
> > different) green dyes, but I used numbers to keep the colors in all
caps,
> so
> > that spacing due to small case g wasn't a problem.)
> >
>
> so you do edge-detection even when you don't have pixels quite ready
yet...
> that's to say, you use edge-detection to help interpolate some missing
> pixels?
>
> in that case my algorithm might not be able to help: it needs some side
> information when all pixels are ready... but I will think about it to
> improve and see if I can use some side information ready inside the CMOS
> sensor at the demosaicing time.
>
> but on the other hand, knowing that a CMOS sensor can be edge-detection
> itself lend me to some other ideas to utilize the functionality of CMOS
> sensor. Would you mind telling me how does edge-detection relate to the
> interpolation of missing pixels in CMOS sensor? Is that only YES/NO answer
> that is needed? I guess the edge-detection should not only fast but also
as
> simple as possible for energy concern?
>
> > Also, in exploring "fast" algorithms that may be extremely
computationally
> > efficient by not "optimal", you are in "engineering-space", rather than
> > "academia-space". You could really patent it if it were much faster than
> the
> > currently accepted "optimal" algorithm, and also "optimal". However,
when
> it
> > is sub-optimal, it moves into the engineering cost/benefit space. That
is,
> I
> > came up with many, many, cool ways to do demosaicing (including edge
> cases),
> > but the one we ended up usinig was the one that had the "best"
> > results/computation-time (given the processor we were using, which we
> would
> > not change) tradeoff, according the marketing and the customers. It was
> not
> > the fastest, and it was not the most performant.
> >
>
> I guess inventing a new algorithm(hopefully I am the first, I am not sure
> myself, also I am not sure if it is useful at all...:=) is
"academia-space",
> tweak existing algorithms for tradeoffs is "engineering-space"... :=)
>
> Regards,
>
> -Jeonyim
>
>

>Jim Gort" <jgort@comcast.net> wrote in message news:87DTb.163184

> I think this is one case of the general problem of interpolation. However,
> since this must be done very very quickly to keep cost of processing power
> down (e.g., in a digital camera), the literature on great interpolation
> methods is mostly unusable, and ad-hoc methods prevail.
>

Hello Jim,

The strategy used currently with digital SLRs is to use a simple demosaicing
algo in the camera to make a .jpg file, but the real trick is to use raw
mode. In raw mode the actual sensor data along with the camera settings are
combined into a file that is demosaiced with a more sophisticated algo in a
PC/Mac. Most pros I know of shoot everything in raw mode and do the post
processing external relative to the camera. In fact the raw files are
treated as digital negatives and clever mechanisms exist for modifying the
raw files in such a way that the original data can always be recovered. I
use Nikon's raw converter for batch processing and it works like a champ.
And the difference between in camera and out of camera demosiacing is
astounding.

-- 
Clay S. Turner, V.P.
Wireless Systems Engineering, Inc.
Satellite Beach, Florida 32937
(321) 777-7889
www.wse.biz
csturner@wse.biz

>

Clay:

Different context--my work was on bottom-of-the-line CMOS digital cameras,
where the goal was for consumer to pay <$50 (for VGA, slightly more for
megapixel), take pictures that did not take more than 10seconds
processing/compression in the camera, download them to garden variety .JPG
viewers, and hopefully they didn't look too cruddy. Focus was on ease-of use
and cost, with image quality secondary, as the market was not imaging
professionals!

In the cameras I worked on, the processing and compression was always done
in the camera, and, though all of the algorithms could have been tweaked
(per user preferences) via a few parameters, these were not generally made
available via the camera UI, since UIs were kept minimal to avoid creating a
consumer device that is overwhelmingly complicated for the average consumer.
The option to download the raw file was avaible only via "secret" button
sequences, which were used by us in developing the processing algorithms
(which was done on a PC using the raws).

However, what you mentioned is a great idea that was never explored where I
worked--offer the user the option to save raws, and give him a PC software
package that would do the processing/compression on the PC, with as much
user control as possible. This would have been a great answer to the
cost/compression time/image quality tradeoff--to the average consumer it
would be a blurb in the manual that was ignored, but to people demanding the
best image quality for their buck, and to the people demanding to see how
good the image quality is (e.g., OEM customers), it would be the preferred
method. In fact the processing/compression on the PC done by the camera
manufacturer could be bypassed, and the true hobbiest could actually explore
his own processing algorithms....

Too bad we (my old company) didn't have that idea, and too bad I'm no longer
working in the digital camera arena. Though you mentioned it for high-end
users, I think it would be a valuable (i.e., "differentiating") addition to
low-end camers too. And software is cheap.

Jim

"Clay S. Turner" <CSTurner@WSE.Biz> wrote in message
news:5oDTb.12842$aU6.7832@bignews3.bellsouth.net...
> >Jim Gort" <jgort@comcast.net> wrote in message news:87DTb.163184
>
> > I think this is one case of the general problem of interpolation.
However,
> > since this must be done very very quickly to keep cost of processing
power
> > down (e.g., in a digital camera), the literature on great interpolation
> > methods is mostly unusable, and ad-hoc methods prevail.
> >
>
> Hello Jim,
>
> The strategy used currently with digital SLRs is to use a simple
demosaicing
> algo in the camera to make a .jpg file, but the real trick is to use raw
> mode. In raw mode the actual sensor data along with the camera settings
are
> combined into a file that is demosaiced with a more sophisticated algo in
a
> PC/Mac. Most pros I know of shoot everything in raw mode and do the post
> processing external relative to the camera. In fact the raw files are
> treated as digital negatives and clever mechanisms exist for modifying the
> raw files in such a way that the original data can always be recovered. I
> use Nikon's raw converter for batch processing and it works like a champ.
> And the difference between in camera and out of camera demosiacing is
> astounding.
>
> --
> Clay S. Turner, V.P.
> Wireless Systems Engineering, Inc.
> Satellite Beach, Florida 32937
> (321) 777-7889
> www.wse.biz
> csturner@wse.biz
>
> >
>
>

"Joenyim Kim" <jeonyimkim80@yahoo.com> wrote in message news:<bvjn1n$bkm$1@mozo.cc.purdue.edu>...
> "Brian Stone" <no.more.spam@stoneentertainment.com> wrote in message
> news:acd67ea1.0401291748.7419c4fc@posting.google.com...
> > "Joenyim Kim" <jeonyimkim80@yahoo.com> wrote in message
> news:<bv8pkf$9t4$1@mozo.cc.purdue.edu>...
> 
> Hi Brian,
> 
> Thank you for your information!
> >
> > We're developing a computer vision algorithm to locate a specific
> > symbol in an image.  The symbol is a circled white X on a black
> > background, and its position, scale, and 3D orientation are unknown in
> > the frame of the photograph.
> 
> This is like targeting and shooting... heh heh :=)

That's not too far from the truth.  We're developing the vision system
for an autonomous helicopter.  The goal is to acquire the target
symbol and "shoot" the helicopter towards it so it can continue with
the next stage of its mission.  We'll be competing in the
International Aerial Robotics Competition at Fort Benning, Georgia
this July.

> > A couple of conventional methods that
> > we've considered using to locate the symbol are the Hough transform
> > and template matching.
> 
> What's the relationship between the circled white X with edge detection?

Edge detection is a first step for many computer vision applications. 
Straight lines, for instance, aren't something that show up in nature
a lot, but they show up all the time in man-made structures.  So, it
makes sense to try to separate these things.  We can use simple facts
like this to eliminate a large percentage of the image, allowing us to
concentrate more powerful (and much slower) algorithms on the pixels
that most likely contain the symbol.  Also, many of these algorithms
work best on edge-enhanced images.

> > If you're not keen on leaking the algorithm, just post the semantics.
> > For example, what do you define as "diagonal"?
> 
> I mean almost 45 degree slope lines.

That's pretty limited.  Does it just search for a 45 diagonal row of
pixels, or can it have some tolerance in the angle?  How strict is it?

> > How well does it deal with noise?
> 
> I am not sure. Your application is like you need to distinguish a circled
> cross from its background. The background itself can be an image. So what if
> the image itself has diagonal edges? My algorithm can not distinguish that
> crossed edge from the edges in image itself...

It seems that you could run your algorithm on a small block of pixels
in the image and get a local response for that block.  You could then
build a bitmap of responses over the entire image.  Is this not
possible?

> > How fast is it compared to similar approaches... can you
> > give test results?
> 
> Should be very very fast; and it likes to work on large images.

Kinda sounds like you haven't coded it yet.  What's the worst,
average, and best-case runtimes you can expect, then?

> >Can it find thick lines?
> 
> I am going to test this... It is an interesting problem. I have not thought
> it before... :=)
>
> >  I'd definitely be
> > interested in hearing.  Although edge detection is probably the most
> > researched subject in image processing, I'm not willing to concede
> > that the best algorithms have already been published.
> 
> Once again, the scope of my algorithm is to find YES/NO answer to the
> question whether an diagonal edge exists or not. It might also work for a
> cross... But it does this in a blockbased method. The speed improvement
> comes from the fact that it just seeks for binary answer.
> 
> Best regards,
> 
> -Jeonyim

It sounds like you need to do a little more research to really know
what you have there.  If you think you've really got something, I
suggest you write a paper about it and publish it on the web.  There
isn't money in algorithms, by the way, only glory.  If you think
you've really, really, really got something, then maybe you should
consider patenting it.  I don't normally endorse patenting of what I
consider "component" algorithms (algorithms that have no direct
application).  But, if a kid can patent a method of swinging sideways
on a playground swing, then someone can surely patent an edge
detector. ;-)

In any case, I wish you luck with it.

-- Brian Stone