Fun with sobel - Neon Effect - Thick Edge Detection

Questions and postings pertaining to the usage of ImageMagick regardless of the interface. This includes the command-line utilities, as well as the C and C++ APIs. Usage questions are like "How do I use ImageMagick to create drop shadows?".
HugoRune
Posts: 90
Joined: 2009-03-11T02:45:12-07:00
Authentication code: 8675309

Fun with sobel - Neon Effect - Thick Edge Detection

Post by HugoRune »

I have been experimenting with the sobel operator, after the helpful tips from Fred and Anthony.
My goal here was to detect only thick edges and ignore small-scale variations.
For example, I have a photo of a text document. I want an edge image with only the border of the document, not the text.

ImageImage

ImageImage


I solved this by
1) generating a series of more and more blurred versions of the original image
2) sobel edge detection on each of these versions
3) multiplying all these sobel images

The result is an edge image, where all small-scale variations have been smoothed out, but all remaining edges are still thin. Ideal for further processing via hough transform.

You can also generate a nice neon effect this way:

ImageImage

(for comparison, a normal sobel result and a convert -edge 1. Note how the small edges from the hair dissapear completely in above picture
ImageImage


The point was this: I needed this edge image as input for my hough transform.
I detect the corners of the quadrangle in this image, and then use that as input for convert -distort perspective, to get the undistorted image:
Image --> Image --> Image

The command line for above pictures:

for the baboon:

Code: Select all

convert  baboon.jpg  ^
    -write mpr:blur0 ^
    -blur 0x3 -write mpr:blur1 ^
    -blur 0x3 -write mpr:blur2 ^
    -blur 0x3 -write mpr:blur3 ^
    -blur 0x3 -write mpr:blur4 ^
    -blur 0x3 -write mpr:blur5 ^
    -blur 0x3 -write mpr:blur6 ^
    -blur 0x3 -write mpr:blur7 ^
    +delete ^
    ( mpr:blur0 mpr:blur1 mpr:blur2 mpr:blur3 mpr:blur4 mpr:blur5 mpr:blur6 mpr:blur7 ^
        -bias 50% -convolve "-0.125,0,0.125,  -0.25,0,0.25,  -0.125,0,0.125" -solarize 50% -level 50%,0% ) ^
    null: ^
    ( mpr:blur0 mpr:blur1 mpr:blur2 mpr:blur3 mpr:blur4 mpr:blur5 mpr:blur6 mpr:blur7  ^
        -bias 50% -convolve "-0.125,-0.25,-0.125,  0,0,0,  0.125,0.25,0.125" -solarize 50% -level 50%,0% ) ^
    -compose plus     -layers composite  ^
    -contrast-stretch 0 ^
    -sigmoidal-contrast 6,50% ^
    -compose multiply -layers flatten ^
    -contrast-stretch 0 ^
baboon-02.jpg
For the other images, I have a little batch file. Since processing these large images is very slow (1 minute per photo), I use a -filter gaussian -resize instead of a blur.

SOBELSERIES.BAT

Code: Select all

for /f "usebackq" %%a in ( ` convert %1 -format "%%wx%%h"  info: ` ) do set size=%%a

echo %1 %time%
convert  %1 -filter gaussian ^
    -write mpr:blur0 ^
    -resize 50%% -write mpr:blur1 ^
    -resize 50%% -write mpr:blur2 ^
    -resize 50%% -write mpr:blur3 ^
    -resize 50%% -write mpr:blur4 ^
    -resize 50%% -write mpr:blur5 ^
    -resize 50%% -write mpr:blur6 ^
    -resize 50%% -write mpr:blur7 ^
    +delete ^
    ( mpr:blur0 mpr:blur1 mpr:blur2 mpr:blur3 mpr:blur4 mpr:blur5 mpr:blur6 mpr:blur7 ^
        -bias 50%% -convolve "-0.125,0,0.125,  -0.25,0,0.25,  -0.125,0,0.125" -solarize 50%% -level 50%%,0%% ) ^
    null: ^
    ( mpr:blur0 mpr:blur1 mpr:blur2 mpr:blur3 mpr:blur4 mpr:blur5 mpr:blur6 mpr:blur7  ^
        -bias 50%% -convolve "-0.125,-0.25,-0.125,  0,0,0,  0.125,0.25,0.125" -solarize 50%% -level 50%%,0%% ) ^
    -compose plus     -layers composite  ^
    -contrast-stretch 0%% ^
    -sigmoidal-contrast 7,50% ^
    -filter mitchell -resize "%size%!" ^
    -compose multiply -layers flatten ^
    -contrast-stretch 0 ^
%2
(all images in this post are heavily resized and compressed)

I am not sure whether this is the optimal method, so if anyone has an idea on a better or faster edge detection like this, please post it here.
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by fmw42 »

Please post your Hough transform solution when finished. Many people have been asking for something like that.

Nice work on muti-scale gradients to reinforce only the large scale objects. Have you experimented with replacing the sobel with a laplacian. There are several 3x3 variants and at least one 5x5 as well as the Mexican hat laplacian for larger sizes. Just curious.


Are you working on an automatic white board capture and perspective correction script. See my whiteboard script. I did not do the auto-detect of the corner points. But the Hough transform is the missing piece on that.
HugoRune
Posts: 90
Joined: 2009-03-11T02:45:12-07:00
Authentication code: 8675309

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by HugoRune »

fmw42 wrote:Please post your Hough transform solution when finished. Many people have been asking for something like that.
I have a working implementation for the perspective correction with hough transform, using python and openCV. It is a mess though. I want to release that after I cleaned it up a bit. Still thinking about how to release it.

It works well, at least for simple cases with homogenous background like this
Image --> Image --> Image

I also have a formula for calculating the correct aspect ratio of the rectangle, http://stackoverflow.com/questions/1194 ... -rectangle
but I have not tested it yet, currently I am using a hard coded aspect ratio for DIN 4A
fmw42 wrote:Nice work on muti-scale gradients to reinforce only the large scale objects. Have you experimented with replacing the sobel with a laplacian. There are several 3x3 variants and at least one 5x5 as well as the Mexican hat laplacian for larger sizes. Just curious.

Are you working on an automatic white board capture and perspective correction script. See my whiteboard script. I did not do the auto-detect of the corner points. But the Hough transform is the missing piece on that.
Automatic perspective correction is what I am working on, although my focus so far has been more on printed documents and beamer presentations. Basically the same problem.

I have been experimenting with the laplacian a lot, but without much success. While sobel is very robust at various blur factors, laplace required a lot of threshold and contrast adjustments depending on blur, and was totally unusable at larger blur settings. That might be because of my limited methods for detecting zero crossings though.
I tried 5x5 laplacian kernels, but the results were in all my test cases significantly worse than with a 3x3 kernel.

I also did some tests with the imagemagick edge detection. One problem is that the edges are only in the white, and with larger blur they shift places.
Basically instead of Sobel I used "-edge X ( +clone -negate -edge X ) -blur Y -compose multiply -composite" for different blur factors. It worked moderately well, but Sobel works better.
I still want to try the same thing with other Difference of Gaussians.

One big advantage of sobel, that I have not utilized yet, is that it can theoretically preserve the edge orientation (i.e. bright-to-dark or dark-to-bright).
I have not yet figured out a good way to do this though.
Would make edge detection more robust, since opposide sides of a paper/whiteboard should have opposite orientation.

This might be esssential for whiteboards, since they often are white in front of a white wall, so my sobel-series script does not work as well.
Zhengyou Zhang and Li-Wei He talk about this problem in "Whiteboard scanning and image enhancement" http://research.microsoft.com/en-us/um/ ... r03-39.pdf
Too bad they do not seem to have released any code.
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by fmw42 »

Yes, we are on the same page (sorry for the pun). I started working on my whiteboard script, but posted something before continuing with the detection of the border (hough transform) corners and the auto aspect ratio.

I found a similar paper by the same authors, http://research.microsoft.com/en-us/um/ ... r03-39.pdf (and I have a good background in 3D perspective, so I believe I can implement something like that) and have intended to get back to the auto aspect correction, but got sidetracked by Magick agreeing to implement the work that Sean Burke and I did with FFT into IM and have been working with him and on all the documentation for FFT with Anthony. So I have not returned to the whiteboard issue. I had not seen your first paper by http://stackoverflow.com/questions/1194 ... -rectangle

One other point that may help. With the use of sobel or any gradient, you can compute the directional derivative which can be used to code the edges you extract with a direction. Then you can use that to prune your edges so that that neighboring pixels follow the same direction. That way you can extract straight edges if you want or just get rid of noise edges near your 4 main edges.

You may want to see both my scripts, whiteboard and textcleaner.

Ultimately, I was hoping to find someone who wanted to collaborate on making it into a iPhone app. Any interest?
HugoRune
Posts: 90
Joined: 2009-03-11T02:45:12-07:00
Authentication code: 8675309

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by HugoRune »

fmw42 wrote:Yes, we are on the same page (sorry for the pun). I started working on my whiteboard script, but posted something before continuing with the detection of the border (hough transform) corners and the auto aspect ratio.

I found a similar paper by the same authors, http://research.microsoft.com/en-us/um/ ... r03-39.pdf
um, isn't that the same paper?
(and I have a good background in 3D perspective, so I believe I can implement something like that) and have intended to get back to the auto aspect correction, but got sidetracked by Magick agreeing to implement the work that Sean Burke and I did with FFT into IM and have been working with him and on all the documentation for FFT with Anthony. So I have not returned to the whiteboard issue. I had not seen your first paper by http://stackoverflow.com/questions/1194 ... -rectangle
The aspect equations are not too bad, althought I would have never been able to come up with them myself. With some assumptions it boils down to 4 manageable equations, my main problem currently is that there is a division by zero in the equation for the focal length if two sides of the distorted rectangle are exactly parallel.
It is no problem if the focal length is known however.

One other point that may help. With the use of sobel or any gradient, you can compute the directional derivative which can be used to code the edges you extract with a direction. Then you can use that to prune your edges so that that neighboring pixels follow the same direction. That way you can extract straight edges if you want or just get rid of noise edges near your 4 main edges.
I think we are talking about the same thing, preserving the edge orientation?
If I understand this correctly (and I am not at all sure I do) the orientation is given by atan2(sobelY,sobelX). I may be able to use this with the fx operator.
Have not tested it so far, might be hard to combine different blur levels.

(edit: some tests with edge orientation at different blur levels, black = vertical, white = horizontal)
(edit2: since I forgot to remove the abs() by -solenoid, these pictures do not show the full orientation range)
ImageImageImageImageImageImage

Code: Select all

convert  lena.jpg ^
    ( -clone 0 ^
        -bias 50%% -convolve "-0.125,0,0.125,  -0.25,0,0.25,  -0.125,0,0.125" -solarize 50%% -level 50%%,0%% ) ^
    ( -clone 0 ^
        -bias 50%% -convolve "-0.125,-0.25,-0.125,  0,0,0,  0.125,0.25,0.125" -solarize 50%% -level 50%%,0%% ) ^
	-delete 0 ^
    -fx "atan2(v,u)/pi/2"  ^
	-contrast-stretch 0 ^
orientb0.png
You may want to see both my scripts, whiteboard and textcleaner.
They are quite useful, but I am not sure I like the strong edges introduced by the -lat. Currently I use the divide method from http://www.imagemagick.org/Usage/compose/#divide to preserve some of the antialiasing, and then do some background separation afterwards.
Ultimately, I was hoping to find someone who wanted to collaborate on making it into a iPhone app. Any interest?
I don't know anything about iphone programming so far, so I cannot really estimate how hard that will be, but I would be interested.
Have you programmed for the iphone before?

Rather surprising that there is no such app for the iphone with all the buzz.
For windows I recently saw some mention of snapter ice. It is closed source, and I have not tested it yet, but judging from the screenshots it sets the bar for a windows app rather high.
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by fmw42 »

I think we are talking about the same thing, preserving the edge orientation?
If I understand this correctly (and I am not at all sure I do) the orientation is given by atan2(sobelY,sobelX). I may be able to use this with the fx operator.
Have not tested it so far, might be hard to combine different blur levels.
Yes that is correct, but note it will have positive and negative values. All my image processing from many years ago was on a system that had no issues with negative values. So it was similar to using HDRI with IM in some regards. So I am not sure at this point what should be done with IM and bias to deal with that. The other issue is do you need to be concerned with any edges that are 180 opposite and thus you could then just atan(sobelY/soblX). Remains to be seen.

I am not much of a programmer. More an image scientist and scripter. So I have never programmed esp for the iPhone, but I have been in contact with a couple of others who have. But so far no interest in doing this or at least collaborating.

My reference was the same article but was in Doc form by the same authors. I am not sure if it is exactly the same as your html reference or a subset. But it looked similar and the equations I believe were the same.

There are some apps like this for other phone systems. I have some references. http://www.shareyourboard.com/how.html
http://www.beetlebugsoftware.com/ (this one is for the iPhone, but does not appear to do the perspective)
http://softtouchit.com/xpe/portal/674ee ... 648aa451c5
They are quite useful, but I am not sure I like the strong edges introduced by the -lat. Currently I use the divide method from http://www.imagemagick.org/Usage/compose/#divide to preserve some of the antialiasing, and then do some background separation afterwards.
That looks like an interesting alternate approach. I never tried that, but seems like it ought to work OK. Are you willing to say how you are processing for background cleanup using the divide and whatever else following that?
The aspect equations are not too bad, althought I would have never been able to come up with them myself. With some assumptions it boils down to 4 manageable equations, my main problem currently is that there is a division by zero in the equation for the focal length if two sides of the distorted rectangle are exactly parallel.
It is no problem if the focal length is known however.
I have not had time to get into those equations yet, but understand the principles. So how do you plan to avoid the divide by zero or get the focal length if you don't have that? Is that for any two sides or the two sides that are involved with perspective? If the latter, then if you find parallel, then perhaps you don't need an aspect change and can just skip that?
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by fmw42 »

here is another interesting way to get the edges of your whiteboard that works in this case, but may not work universally.

whiteboard_international.jpg
Image

#get saturation channel

convert whiteboard_international.jpg -colorspace HSB -channel G -separate whiteboard_international_hsb_1.png
Image

# threshold at 50%
convert whiteboard_international_hsb_1.png -threshold 50% whiteboard_international_hsb_1_t50.png
Image

# apply 10 iterations of morphologic close to clean up small dark areas
morphology -t close -i 10 whiteboard_international_hsb_1_t50.png whiteboard_international_hsb_1_t50_close10.png.png
Image

# extract edges
convert whiteboard_international_hsb_1_t50_close10.png.png -edge 1 whiteboard_international_hsb_1_t50_close10_edge1.png
Image
HugoRune
Posts: 90
Joined: 2009-03-11T02:45:12-07:00
Authentication code: 8675309

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by HugoRune »

I have not had time to get into those equations yet, but understand the principles. So how do you plan to avoid the divide by zero or get the focal length if you don't have that? Is that for any two sides or the two sides that are involved with perspective? If the latter, then if you find parallel, then perhaps you don't need an aspect change and can just skip that?
Not sure I understand, aren't all sides involved with perspective? If both pairs of sides are parallel, the aspect ratio is unchanged. If only one pair of sides is parallel (only one vanishing point at infinity) then it is problematic. Chances are that no two sides will line up exactly parallel in a photo, and I could jiggle the points a bit if it happens, but it is an inelegant solution.
Another way to deal with is to take multiple photos of the same object and average aspect ratio. Or calibrate the camera to determine focal length.
That looks like an interesting alternate approach. I never tried that, but seems like it ought to work OK. Are you willing to say how you are processing for background cleanup using the divide and whatever else following that?
currently i use something like this, but I fiddle around with it depending on input

Code: Select all

for %a in (*.png) do convert %a 
    ( +clone  -scale 12.5% -blur 0x5 -resize 800% )    // large scale blur. Should be bigger than any foreground object.
    +swap -compose divide -composite  // makes background white. 

    ( -clone 0 -contrast-stretch 2%,50% -threshold 50% 
        // create background mask. -lat might work better here, but is slow
		
        -blur 4x2 -threshold 99%       // erode background mask
        -blur 4x2                      // blur eroded background mask
    ) -compose screen -composite // remove noise in background
	-contrast-stretch 0 ..\scan1cleaned\%a  
	
for %a in (*.png) do 
     for /f "usebackq" %b in 
     (`convert %a ..\..\trimmask.png -compose over -composite -blur 0x2 -fuzz 30% -trim -border 30x30 -repage "!-30-30" -format "%wx%h%O" info:`) do 
          convert %a -crop %b -flatten ..\scan2whiteborder\%a 
(trimmask.png is a mostly transparent image with a small white border, and larger white corners, and two white rectangles where puncher holes in a page usually are.)
Main problem with divide is the same problem as with -lat: big foreground objects get white holes.
One solution would be to fill the background with a floodfill transparent,
invert alpha so that the foreground is transparent,
blur and remove alpha to get a blurred image with the foreground removed,
and then use this image as the divisor. Didn't bother so far.

here is another interesting way to get the edges of your whiteboard that works in this case, but may not work universally.
seems a bit situational. The wall in this picture happens to be yellow, but often they have some low saturation like dull gray or white. The slide background can be colored too
Brightness might be a a safer bet, since a beamer projection has to be brighter than the wall. Not so effective for papers or whiteboards though.

The morphological close is a good idea. I am surprised how little it shifts the edges.
I might try this in combination with determining the average RGB and HSB values of the center region and the border, finding the largest discrepancy and choosing a threshold based on that.
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by fmw42 »

Not sure I understand, aren't all sides involved with perspective? If both pairs of sides are parallel, the aspect ratio is unchanged. If only one pair of sides is parallel (only one vanishing point at infinity) then it is problematic. Chances are that no two sides will line up exactly parallel in a photo, and I could jiggle the points a bit if it happens, but it is an inelegant solution.
Another way to deal with is to take multiple photos of the same object and average aspect ratio. Or calibrate the camera to determine focal length.
Just wanted to know if it happened if two sides were parallel and the other two not as in one vanishing point. I was not sure if you meant that case or when both sets of opposite sides were parallel and thus only happening when no perspective
seems a bit situational.
Yes, I agree, but your test images so far (not counting the mandril) have been too easy -- too much contrast between the area of interest and the background.

Try your edge technique and your whiteboard on some of the images that I used for my whiteboard script. I would be curious about the results and comparison of the background removal as well as your ability to get the whiteboard boundary. I also have some others that are harder. Some have barrel distortion, so the hough straight line approach won't work well unless barrel is corrected first.
HugoRune
Posts: 90
Joined: 2009-03-11T02:45:12-07:00
Authentication code: 8675309

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by HugoRune »

Some tests with whiteboards.
cleaning was done with

Code: Select all

for %a in (*-hough.*) do convert "%a" ^
    ( +clone  -scale 12.5% -blur 0x30 -resize 800% ) ^
    +swap -compose divide -composite ^
    ( -clone 0 -contrast-stretch 2%,50% -threshold 60% ^
        -blur 4x2 -threshold 99% ^
        -blur 4x2 ^
    ) -compose screen -composite ^
    -contrast-stretch 0% "%~na-clean.png"
[/size]
Image
ImageImageImageImage
As expected, some confusion about the double edges, might be solvable with edge orientation information

Image
ImageImageImageImage
I am surprised that actually worked. My sobel script needs contrast between object and background, and it's all yellow. There is much less edge noise than in a normal printed page though, so hough still finds the correct edges (except top)

Image
ImageImage
Failure due to missing upper edge. At least the missing lower left corrner and distorted vertical edges would not have been a problem in this case.
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by fmw42 »

your cleaning results are pretty good. just a little spotty on the first one, but I had trouble too

edge direction may help in separating the double border from the wood on the first one.

you have a lot of lines and color dots drawn on each example. is that manually or from your Hough transform. if the latter, when and if you are willing to post, I would be very interested in the complexity of how you solved that and then for the corners and how you throw out false intersections. How much comes from openCV? So your solution relies upon other tools to do a lot of the work in that regard?

But nice work.

I will have to experiment with your cleaning technique and make some comparisons with mine.
HugoRune
Posts: 90
Joined: 2009-03-11T02:45:12-07:00
Authentication code: 8675309

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by HugoRune »

The colored lines are the debugging output from my script.

It is about 400 lines, could be shorter, and uses openCV for canny edge detect, hough transform and graphic display.

It uses imagemagick, but currently by calling sobelseries.bat and convert.exe through the shell. I want to use the imagemagick python interface instead, but do not know when I get around to that.

I did not implement my own hough transform, but I probably should, because the opencv one is lousy. No working Non-Maximum-Supression, and no way to access the accumulator values for each line, just their order. No simple way to use orientation information for hough transform either.

The algorithm for selecting the best quadrangle was created by me, and is a bit hacked, but it seems to work. Basically I sort the lines by strength, take the strongest detected line, and keep adding lines that satisfy all quadrangle criteria
(like, all quadrangle sides must be longer than X, all corners must be >30°, must be convex)

There are currently no sanity checks for command line paramters, and in case of any error it simply crashes.
Only rudimentary comments, and the code is a mess.
The quadrangle detection and the preprocessing could be improoved a lot.
Aspect ratio recognition has not been iintegrated, and currently it simply maps all rectangles to 1682x2378 pixels (DIN A4)

But it worked for all the photographed pages I threw at it.

I want to make some of these changes and then make an official release, but I do not know how soon I get around to that.
Might be a while, since the original reason I made this script was the thousands of pages I photographed, and I still have to read them all.

Here is a little preview, feedback welcome:

Code: Select all

#!/usr/bin/python
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.
#
################################################################
#
# This is a standalone program.  
# it requires 
# - python 2.6+ ( 2.5 or 2.4 works probably too)
# - openCV with PythonInterface installed
# - imagemgagick with convert somewhere in the path (only required for batch processing)
# - sobelseries.bat in the same directory or somewhere in the path (only required for batch processing)
# 
################################################################
#
# USAGE:
#
# 1) DISPLAY
# houghlines.py IMAGEFILE
#      use hough transform to detect lines in the image, 
#      identify most prominent perspective-distorted rectangle, 
#      display results on screen, wait for keypress
#
# 2) BATCH PROCESSING
# houghlines.py INFILE OUTFILE
#     use sobelseries.bat to filter nonrelevant edges, (NEEDS SOBELSERIES.BAT)
#     identify most prominent rectangle,
#     correct perspective in INFILE, write results to OUTFILE  (NEEDS IMAGEMAGICK)

import sys
import subprocess
import os
from math import sin,cos,sqrt,degrees,radians
from opencv.cv import *
from opencv.highgui import *

# Find point (x,y) where two parameterized lines intersect 
# lines are given i the hough form (rho,theta)
# returrns None for parallel lines
def intersectLines2(r1, t1, r2, t2) :
	ct1=cos(t1)
	st1=sin(t1)
	ct2=cos(t2)
	st2=sin(t2)
	d=ct1*st2-st1*ct2
	if abs(d)>0.000001 :   
		x = ((st2*r1-st1*r2)/d)
		y = ((-ct2*r1+ct1*r2)/d)
		return (x,y)
	else: #lines are parallel
		return None

def intersectLines(line1,line2):
	return intersectLines2(line1[0],line1[1],line2[0],line2[1])

		
#returns true if the point is within the given axis-aligned rectangle. all points are tuples
def pointInRect(point,rect):
	topLeft,bottomRight = rect
	if point[0]>=topLeft[0] and point[1]>=topLeft[1] and point[0]<=bottomRight[0] and point[1]<=bottomRight[1]:
		return True
	else: return False


def angledist(theta1,theta2):
	return abs( (theta1 + CV_PI/2 - theta2) % CV_PI - CV_PI/2 )
	# print degrees(angledist(radians(0),radians(0))),"=0"
	# print degrees(angledist(radians(0),radians(90))),"=90"
	# print degrees(angledist(radians(0),radians(180))),"=0"
	# print degrees(angledist(radians(0),radians(270))),"=90"
	# print degrees(angledist(radians(0),radians(360))),"=0"
	# print degrees(angledist(radians(0),radians(179))),"=1"
	# print degrees(angledist(radians(0),radians(181))),"=1"

	# print degrees(angledist(radians(180),radians(0))),"=0"
	# print degrees(angledist(radians(180),radians(90))),"=90"
	# print degrees(angledist(radians(180),radians(180))),"=0"
	# print degrees(angledist(radians(180),radians(270))),"=90"
	# print degrees(angledist(radians(180),radians(360))),"=0"
	# print degrees(angledist(radians(180),radians(-1))),"=1"
	# print degrees(angledist(radians(180),radians(1))),"=1"

	# print degrees(angledist(radians(-180),radians(0))),"=0"
	# print degrees(angledist(radians(-180),radians(90))),"=90"
	# print degrees(angledist(radians(-180),radians(180))),"=0"
	# print degrees(angledist(radians(-180),radians(270))),"=90"
	# print degrees(angledist(radians(-180),radians(360))),"=0"
	# print degrees(angledist(radians(-180),radians(-1))),"=1"
	# print degrees(angledist(radians(-180),radians(1))),"=1"


def angle_deg(line1,line2):
	return  angledist(line1[1] ,line2[1]) / CV_PI * 180


#this does not work in some cases
def rhodist(rho1,rho2):
	#return abs( abs(rho1)-abs(rho2) )
	return abs( rho1-rho2 )
	
def pointdist(p1,p2):
	return sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)
	

# not used anymore
def sortQuadranglePoints2(pointlist):
	"""
	  a-------b
	  |       |
	  |       |
	  c-------d
	"""
	# sort 4 points so that
	# a = from the leftmost points, the topmost
	# b = from the topmost points, the leftmost
	# d = from the rightmost points the topmost
	# c = last point
	
	points = pointlist[0:4]
	points.sort()
	a = points.pop(0)
	points.sort(key=lambda p: (p[1],p[0]))
	b = points.pop(0)
	points.sort(key=lambda p: (-p[0],p[1]))
	d = points.pop(0)
	c = points.pop(0)
	print " %1.4f,%1.4f 0,0 %1.4f,%1.4f 1000,0 %1.4f,%1.4f 1000,1000 %1.4f,%1.4f 0,1000 " % (a[0],a[1],b[0],b[1],d[0],d[1],c[0],c[1])
	return a,b,c,d

def sortQuadranglePoints(pointlist):
	"""
	  a-------b
	  |       |
	  |       |
	  c-------d
	"""
	# sort 4 points so that
	# a = topleftmost point
	# b = from the remaining points, the toprightmost point
	# d = from the remaining points, the bottomrightmost point
	# c = last point
	
	points = list(pointlist[0:4])
	points.sort(key=lambda p: (p[0]+p[1],p[0]))
	a = points.pop(0)
	points.sort(key=lambda p: (-p[0]+p[1],p[1]))
	b = points.pop(0)
	points.sort(key=lambda p: (-p[0]-p[1],-p[0]))
	d = points.pop(0)
	c = points.pop(0)
	return a,b,c,d
		


# picks a rectangel from an ordered list of points
# algorithm:
# - start with the first line
# - keep adding lines that satisfy rectangle criteria
# returns the 4 corner points or None
def pickQuadrangle(houghlines,width,height):
	"""
	  a-------b  b-------a
	  |       |  |       |
	  |       |  |       |
	  c-------d  d-------c
	"""
	# at the end the corner points will be ordered abdc clockwise or counterclockwise
	a,b,c,d = None,None,None,None # corner points
	vanish1,vanish2 = None,None # vanishing points
	ab,ac,bd,cd = None,None,None,None # lines
	
	mindist  =min (width,height) / 6 # minimum lengt of one side
	bigrect  =(-width/4,-height/4),(width*1.25,height*1.25) # the 4 corners have to be in this area
	smallrect=(width/4,height/4),(width*0.75,height*0.75) # the 2 vanishing points have to be outside this area

	lines = houghlines[:] 
	
	
	for dummy in 0, :
		#pick the strongest line as ab
		if len(lines)>0: 
			ab = lines.pop(0)
			print "found ab", ab
		else: 
			break

		for line in lines:
			# pick line ~perpendicular to first line (angle + pointinrect):
			ac = line
			if angle_deg (ab , ac) < 45 : continue

			a = intersectLines (ab , ac)
			if not a or not pointInRect (a , bigrect) : continue

			print "found ac", ac
			break
		else: 
			ac = None; a = None
			break
		lines.remove(ac)

		for line in lines:
			# pick line ~perpendicular to either line 
			bd = line
			if angle_deg (ac , bd) > 30 : (ab,ac) = (ac,ab)
			if angle_deg (ab , bd) < 30 : continue
			
			
			b = intersectLines (ab , bd)
			if not b or not pointInRect (b , bigrect) : continue
			if pointdist (b , a) < mindist : continue
			
			vanish1 = intersectLines (ac , bd)
			# vanishing point  should be None or far away
			if vanish1 and pointInRect (vanish1 , smallrect) : continue

			print "found bd", bd
			break
		else: 
			bd = None; b = None; vanish1 = None
			break
		lines.remove(bd)

		for line in lines:
			# pick line perpendicular to ac AND bd:
			cd = line

			if angle_deg (ac , cd) < 30 : continue
			if angle_deg (bd , cd) < 30 : continue
			
			c = intersectLines (cd , ac)
			if not c or not pointInRect (c , bigrect) : continue
			if pointdist (c , a) < mindist : continue
			if pointdist (c , b) < mindist : continue

			d = intersectLines (cd , bd)
			if not d or not pointInRect (d , bigrect) : continue
			if pointdist (d , a) < mindist : continue
			if pointdist (d , b) < mindist : continue
			if pointdist (d , c) < mindist : continue

			vanish2 = intersectLines (cd , ab) 
			# vanishing point  should be None or far away
			if vanish2 and pointInRect( vanish2 , smallrect) : continue

			print "found cd", cd
			break
		else: 
			cd=None; c=None; d=None; vanish2=None
			break
		lines.remove(cd)
	else: return (a,b,c,d)
	
	print "NOT ENOUGH LINES"
	return None
	

#convert s  a openCv data structure into a proper python list of tupples
def convertCVList(linesCV):
	lines=[]
	for line in linesCV: lines.append((float(line[0]),float(line[1])))
	return lines

# check if a line is similar to some other lines
def distinctLine(line,goodlines,min_rho_dist,min_theta_dist):
	rho2,theta2 = line
	for rho1,theta1 in goodlines:
		if rhodist(rho1,rho2)<min_rho_dist and angledist(theta1,theta2)<min_theta_dist:
			return False
	return True


# from an ordered list of lines , remove all lines that are "very similar" to an earlier line.
# makeshift Non-Maximum-Supression
def filterLines(lines,min_rho_dist,min_theta_dist):
	goodlines=[]
	for line in lines: 
		if distinctLine(line,goodlines,min_rho_dist,min_theta_dist): goodlines.append(line)

	return goodlines
		


if __name__ == "__main__":
	filename = "testhough.jpg"
	if len(sys.argv)>1:
		filename = sys.argv[1]
		
	if len(sys.argv)>2:
		cmdline = "sobelseries.bat",sys.argv[1],"tmpsobel.png"
		try: os.remove("tmpsobel.png")
		except Exception: pass
		print "> ",cmdline
		subprocess.check_call(cmdline,shell=True)
		filename = "tmpsobel.png"

	src=cvLoadImage(filename, 0);
	if not src:
		print "Error opening image %s" % filename
		sys.exit(-1)

	dst = cvCreateImage( cvGetSize(src), 8, 1 );
	color_dst = cvCreateImage( cvGetSize(src), 8, 3 );
	color_dst_small = cvCreateImage( cvSize(min(src.width,1000),min(src.height,900)), 8, 3 );
	storage = cvCreateMemStorage(0);
	
	#cvCanny( src, dst, 20, 50, 3 );
	cvCanny( src, dst, 50, 200, 3 );
	#cvCanny( src, dst, 100, 1000, 3 );
	#dst=src

	#lines = cvHoughLines2( dst, storage, CV_HOUGH_STANDARD, 1, CV_PI/180, 100, 0, 0 );
	#lines = cvHoughLines2( dst, storage, CV_HOUGH_MULTI_SCALE, 10, CV_PI/180, 100, 10, 11 );
	linesCV = cvHoughLines2( dst, storage, CV_HOUGH_STANDARD, 1, CV_PI/180 , 50, 0, 0 );
	lines=convertCVList(linesCV)

	min_rho_dist=100
	min_theta_dist=radians(10)

	
	goodlines=filterLines(lines,min_rho_dist,min_theta_dist)
	quadranglePoints = pickQuadrangle(lines,src.width,src.height)

	if quadranglePoints: 
		a,b,c,d = sortQuadranglePoints(quadranglePoints)
		print a,b,c,d
		if pointdist(a,b) + pointdist(c,d) > pointdist(a,c) + pointdist(b,d):
			#landscape
			perspectivestring =  "%1.2f,%1.2f 1682,0 %1.2f,%1.2f 1682,2378 %1.2f,%1.2f 0,0 %1.2f,%1.2f 0,2378" % (a[0],a[1],b[0],b[1],c[0],c[1],d[0],d[1]) 
		else:
			perspectivestring =  "%1.2f,%1.2f 0,0 %1.2f,%1.2f 1682,0 %1.2f,%1.2f 0,2378 %1.2f,%1.2f 1682,2378" % (a[0],a[1],b[0],b[1],c[0],c[1],d[0],d[1]) 
		print perspectivestring
	if len(sys.argv)>2:
			cmdline = "convert",sys.argv[1],"-set option:distort:viewport 1682x2378","-distort perspective \"" + perspectivestring + "\"",sys.argv[2]
			print "> ", cmdline
			subprocess.check_call( " ".join(cmdline),shell=True)

	
	if len(sys.argv)<>3:
		cvCvtColor( dst, color_dst, CV_GRAY2BGR );

		for i in range(min(len(goodlines), 100)-1, -1, -1):
			line = goodlines[i]
			#print line[0], round(line[1]/CV_PI*180)
					
			rho = line[0];
			theta = line[1];
			pt1 = CvPoint();
			pt2 = CvPoint();
			a = cos(theta);
			b = sin(theta);
			x0 = a*rho 
			y0 = b*rho
			pt1.x = cvRound(x0 + 5000*(-b));
			pt1.y = cvRound(y0 + 5000*(a));
			pt2.x = cvRound(x0 - 5000*(-b));
			pt2.y = cvRound(y0 - 5000*(a));
			linecolor=CV_RGB(255-min(255*i/10,200),0,255*i/10)
			cvLine( color_dst, pt1, pt2, linecolor, 4, 8 );


		def makeCvPoint(point):
			cvpoint = CvPoint()
			cvpoint.x = cvRound(point[0])
			cvpoint.y = cvRound(point[1])
			return cvpoint

		if quadranglePoints: 

			a,b,c,d = sortQuadranglePoints(quadranglePoints)
			cvCircle (color_dst, makeCvPoint(a), 20, CV_RGB(255,0,0), -1)
			cvCircle (color_dst, makeCvPoint(b), 20, CV_RGB(255,255,0), -1)
			cvCircle (color_dst, makeCvPoint(c), 20, CV_RGB(0,255,0), -1)
			cvCircle (color_dst, makeCvPoint(d), 20, CV_RGB(0,0,255), -1)

			for x1,y1 in quadranglePoints:
				for x2,y2 in quadranglePoints:
					if x1!=x2 or y1!=y2:
						pt1 = CvPoint()
						pt2 = CvPoint()
						pt1.x=cvRound(x1)
						pt1.y=cvRound(y1)
						pt2.x=cvRound(x2)
						pt2.y=cvRound(y2)
						cvLine( color_dst, pt1, pt2, CV_RGB(0,255,255), 2, 8 );

			
		else:
			#lines = cvHoughLines2( dst, storage, CV_HOUGH_PROBABILISTIC, 1, CV_PI/180, 50, 40, 5 );
			lines = cvHoughLines2( dst, storage, CV_HOUGH_PROBABILISTIC, 1, CV_PI/180, 10, 50, 1000 );
			cvCvtColor( dst, color_dst, CV_GRAY2BGR );
			for i in range(min(lines.total, 10)-1, -1, -1):
				line = lines[i]
				linecolor=CV_RGB(255-min(255*i/10,200),0,255*i/10)
				cvLine( color_dst, line[0], line[1], linecolor, 5, 8 );

		cvNamedWindow( "Source", 1 );
		cvShowImage( "Source", src );

		cvResize ( color_dst, color_dst_small)
		cvNamedWindow( "Hough", 1 );
		cvShowImage( "Hough", color_dst_small );

		cvWaitKey(0);
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by fmw42 »

That is a lot of hard work! I think you have done a great job getting what you have as this is not an easy problem.

But the fact that it uses openCV and perhaps Python is going to limit its use with IM users. But don't let this comment deter you. Use what you need to get the job done.

I was just hoping you had developed something that could be folded into IM as IM needs a good Hough Transform and other feature detection tools. But that may be beyond the scope of IM as it is really an image processor not feature detector.
I did not implement my own hough transform, but I probably should, because the opencv one is lousy. No working Non-Maximum-Supression, and no way to access the accumulator values for each line, just their order. No simple way to use orientation information for hough transform either.
Too bad as that is usually important.
HugoRune
Posts: 90
Joined: 2009-03-11T02:45:12-07:00
Authentication code: 8675309

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by HugoRune »

But the fact that it uses openCV and perhaps Python is going to limit its use with IM users. But don't let this comment deter you. Use what you need to get the job done.
Well the idea was that when this program is released, the imagemagick and openCV libraries can be bundled with it, so the user only needs python installed.
With py2exe, not even that.

I was just hoping you had developed something that could be folded into IM as IM needs a good Hough Transform and other feature detection tools. But that may be beyond the scope of IM as it is really an image processor not feature detector.
Folding hough transform into IM hadn't occcured to me, I do not think that would be a good match. The final output you usually want is a list of lines, so nothing that can be easily manipulated with imagemagick. Not to mention the extended hough transforms where the hough space has more than 2 dimensions.
Nevertheless, I think a representation of basic hough line space might be doable with the fx operator, if it somehow allows referencing pixel values in the output image for reading.
someting like -fx "output.p{func1(u),func2(u)} = output.p{func1(u),func2(u)} + u"
where func1 und func2 are the equation "i cos(theta) + j sin(theta) = rho" solved for rho and theta, and u is an edge image with all edge pixels=1 and all other pixels=0
Not sure if the fx operator can do this
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Fun with sobel - Neon Effect - Thick Edge Detection

Post by fmw42 »

Folding hough transform into IM hadn't occcured to me, I do not think that would be a good match. The final output you usually want is a list of lines, so nothing that can be easily manipulated with imagemagick. Not to mention the extended hough transforms where the hough space has more than 2 dimensions.
Nevertheless, I think a representation of basic hough line space might be doable with the fx operator, if it somehow allows referencing pixel values in the output image for reading.
someting like -fx "output.p{func1(u),func2(u)} = output.p{func1(u),func2(u)} + u"
where func1 und func2 are the equation "i cos(theta) + j sin(theta) = rho" solved for rho and theta, and u is an edge image with all edge pixels=1 and all other pixels=0
Not sure if the fx operator can do this
Right, that was why I did not think IM was necessarily appropriate. What you really want out of the Hough is the definition of the lines as rho, theta pairs. But this does not give the line lengths. Lines are infinite or at least as long as necessary until they hit the edges of the image. In your case all you really just want are the intersections which you can get from "infinite" lines.

But what you get from an image is the gradient direction at each pixel. You can prune that with thresholding on the basis or gradient magnitude and even threshold the directions (perhaps as few as 8 ). Then you have to transform each direction for a given location to rho, theta and accumulate the pixels that have the same rho,theta. I suspect that one could do the gradient direction at x,y to rho,theta on an image. But the accumulator is the hard part within IM. Then you need to sort to get the highest accumulated values from the image. Then redraw the lines or find intersections. The rho,theta transform is just a means to an end and has little significance on its own.

I believe that Magick has implemented something a little similar using the radon transform to deskew an image. See http://en.wikipedia.org/wiki/Radon_transform. It is basically doing a similar kind of transformation to find directions of certain features in an image and reorient the image. Works for small rotations. See -deskew

So I suppose something like the Hough transform could be implemented. But then one still has to process the image to get the strong edges and their rho,thetas.

I have not had time to really look into this much even to do the rho,theta transform from the edge gradient directions. But am glad there are others who have an interest.
Post Reply