Canny edge detector: Difference between revisions

Line 681:

</ul>

<lang J>NB. 2D convolution, filtering, ...

NB. 2D convolution, filtering, ...

convolve =: 4 : 'x apply (($x) partition y)'

partition=: 4 : '2 1 3 0 |: (1{x) ]\ 2 1 0 |: (0{x) ]\ y'

partition =: 4 : '2 0 3 1 |: ((1{x) ([+\]) (2 0 1|: ((0{x) ([+\]) y)))'

apply=: 4 :'+/+/x*y'

~~max3x3~~ =: 3 : '~~(0<~~1~~{1{y)~~ * ~~>./>./~~y'

apply =: 4 : '+/"1 (+/"2 (x *"2 y))'

max3x3 =: 3 : '(1{1{y>0) * (>./,y)'"2

partition=: 2 1 3 0 |: {:@[ ]\ 2 1 0 |: {.@[ ]\ ]

apply=: [: +/ [: +/ *

max3x3 =: 3 : '(0<1{1{y) * (>./>./y)'

addborder =: (0&,@|:@|.)^:4

normalize =: ]%+/@,

resample =: 4 : '|: (1{-x)(+/%#)\ |: (0{-x)(+/%#)\ y'

attach =: 3 : 'max3x3 (3 3 partition (addborder y))'

unique =: 3 : 'y*i.$y'

connect =: 3 : 'attach^:_ unique y'

NB. on low memory devices, cropping may be needed

crop =: 4 : 0

'h w h0 w0' =: x

|: w{. w0}. |: h{. h0}. y

)

NB. on small screen devices, image may need to be expanded for viewing

attach =: 3 : 'max3x3 (3 3 partition (addborder y))'

~~unique~~ =: 3 : ~~'y*i.$y'~~

inflate1 =: 4 : 0

~~connect~~ =: 3 : '~~attach^~~:~~_ unique~~ y'

'h w' =: $y

r =: ,y

octant =: 3 : '4|(>.(_0.5+((4%(o. 1))*(12&o. y))))' NB. eighth of circle

c =: #r

~~canny~~ =: 3 : 0

rr =: (c$x) # r

~~image0 =: y~~

(h,x*w)$rr

)

inflate =: 4 : '|: x inflate1 (|: x inflate1 y)'

NB. Step 1 - gaussian smoothing

step1 =: 3 : 0

NB. Gaussian kernel (from Wikipedia article)

gaussianKernel =~~. 159 %~~ 5 5$2 4 5 4 2 4 9 12 9 4 5 12 15 12 5 4 9 12 9 4 2 4 5 4 2

<] gaussianKernel =: 5 5$2 4 5 4 2 4 9 12 9 4 5 12 15 12 5 4 9 12 9 4 2 4 5 4 2

~~image1~~ =: gaussianKernel ~~convolve~~ ~~image0~~

gaussianKernel =: gaussianKernel % 159

gaussianKernel convolve y

)

NB. Step 2 - gradient

step2 =: 3 : 0

gradientKernel =. 3 3$0 _1 0 0j_1 0 0j1 0 1 0

<] gradientKernel =: 3 3$0 _1 0 0j_1 0 0j1 0 1 0

~~image2 =:~~ gradientKernel convolve ~~image1~~

gradientKernel convolve y

)

NB. Step 3 - edge detection

step3 =: 3 : 0

NB. find the octant (eighth of circle) in which the gradient lies

NB. test pattern <(i:6)(4 : 'octant (x j. y)')"0/(i:6)

octant =: 3 : '4|(>.(_0.5+((4%(o. 1))*(12&o. y))))'

<(i:6)(4 : 'octant (x j. y)')"0/(i:6)

NB. is this gradient greater than [the projection of] a neighbor?

greaterThan =: 4 : ' (9 o.((x|.y)%y))<1'

NB. is this gradient the greatest of immmediate colinear neighbore?

greatestOf =: 4 : '(x greaterThan y) *. ((-x) greaterThan y)'

NB. find the octant (eighth of circle) in which the gradient lies

og =: octant image2

NB. relative address of neighbor, per gradient direction

nbr =: 4 2 $ _1 0, _1 _1, 0 _1, 1 _1

NB. relative address of neighbor relevant to grad direction

NB. mask for maximum colinear gradient

krnl0 =. _1 0

ok0 =: (0=og) *. (0{nbr) greatestOf image2

krnl1 =. _1 _1

ok1 =: (1=og) *. (1{nbr) greatestOf image2

krnl2 =. 0 _1

ok2 =: (2=og) *. (2{nbr) greatestOf image2

krnl3 =. 1 _1

ok3 =: (3=og) *. (3{nbr) greatestOf image2

image3 =: image2 *. (ok0 +. ok1 +. ok2 +. ok3)

NB. Step 4 - Weak edge suppression

image =. y

og =. octant image

NB. mask for maximum gradient colinear with gradient

ok0 =. (0=og) *. krnl0 greatestOf image

ok1 =. (1=og) *. krnl1 greatestOf image

ok2 =. (2=og) *. krnl2 greatestOf image

ok3 =. (3=og) *. krnl3 greatestOf image

image *. (ok0 +. ok1 +. ok2 +. ok3)

)

NB. Step 4 - Weak edge suppression

step4 =: 3 : 0

magnitude =. 10&o. y

NB. weak, strong threshholds

NB. TODO: parameter picker algorithm or helper

threshholds =. 1e14 1e15

nearbyKernel =: 3 3 $ 4 1 4 # 1 0 1

nearbyKernel =. 3 3 $ 4 1 4 # 1 0 1

magnitude =. 10&o. image3

weak =. magnitude > 0{threshholds

strong =. magnitude > 1{threshholds

strongs =. addborder (nearbyKernel convolve strong) > 0

~~image4 =:~~ strong +. (weak *. strongs)

strong +. (weak *. strongs)

)

NB. ~~Detect~~ the edges ~~(sets of connected points)~~

NB. find the edges

step5 =: connect

canny =: 3 : 0

image5 =: connect image4

image =. y

image =. step1 image

image =. step2 image

image =. step3 image

image =. step4 image

image =. step5 image

)

</lang>

The above implementation solves the 'inner problem' of Canny Edge Detection in the J language, with no external dependencies. Standard libraries provide additional support including interfaces to image file formats and graphic displays.

</lang>

Image file libraries for different image formats import into and export from a generalized data structure, an array of pixels with three or four color channels. The following code invokes these standard libraries, and also converts between the import format and the monochromatic representation used here for edge detection.

The above implementation solves the 'inner problem' of Canny Edge Detection in the J language, with no external dependencies. J's Qt IDE provides additional support including interfaces to image file formats, graphic displays, and the user. The following code exercises these features

The file 'valve.png' referenced in this code is from one of several Wikipedia articles on edge detection. It can be viewed at [https://upload.wikimedia.org/wikipedia/commons/2/2e/Valve_gaussian_%282%29.PNG[https://upload.wikimedia.org/wikipedia/commons/2/2e/Valve_gaussian_%282%29.PNG]]

require 'gl2'

NB. viewers

coclass 'edge'

require'viewmat'

coinsert'jgl2'

view =: (16b010101*i.256)&viewmat

PJ=: jpath '~Projects/edges/' NB. optionally install and run as project under IDE

NB. image file importers

load PJ,'canny.ijs'

require'png jpeg bmp'

run=: 3 : 0

NB. sample images

wd 'pc form;pn canny'

NB. image =: readbmp 'chess.bmp'

wd 'cc txt static;cn "Canny in J";'

NB. image =: readpng 'boat1.png'

wd 'cc png isidraw'

NB. image =: readjpeg 'lena.jpg'

~~image~~ =: ~~readpng~~ ~~'valve.png~~'

wd 'cc inc button;cn "Next";'

wd 'pshow'

NB. select or combine from color channels

glclear''

NB. if original image is grayscale, take any color channel

image =: readimg_jqtide_ PJ,'valve.png'

red =: <. image % (256^2)

~~green~~ =: ~~256~~ | <. ~~image~~ % ~~256~~

image =: 240 360 120 150 crop image

~~blue~~ =: 256 | image

edges =: canny 256 | image

ids =: }. ~.,edges

image =: blue

nids =: # ids

case =: 0

)

form_inc_button =: 3 : 0

NB. detect the edges

select. case

case. 0 do.

wd 'set txt text "original image";'

img =: 255 setalpha image

case. 1 do.

wd 'set txt text "points on edges";'

img =: edges>0

img =: 1-img

img =: img * (+/ 256^i.3) * 255

img =: 255 setalpha img

ix =: 0

case. 2 do.

wd 'set txt text "... iterating over edges ...";'

img =: edges=ix{ids

whilst. (num<75) *. (ix<nids) do.

img =: edges=ix{ids

num =: +/,img

ix=:>:ix

if. ix=#ids do. case=:_1 end.

end.

img =: 1-img

img =: img * (+/ 256^i.3) * 255

img =: 255 setalpha img

ix =: (#ids)|(>:ix)

end.

if. case<2 do. case =: >: case end.

glfill 255 128 255

glpixels 0 0,(|.$img), ,img

glpaint''

)

form_close=: exit bind 0

load'canny.ijs'

edges =: canny image

viewmat edges

NB. get identifiers of edges

run''</lang>

NB. show edge identifiers

}.~.,edges

1 13963 12701 2564 8279 5752 60 3262 114 7175 13520 221 860 236 12958 1220 14609 14217 18983 47035 4648 3386 22878 11578 7160 12015 8285 7791 12257 9550 10363 11360 12901 12080 17305 13895 17056 30593 24059 17064 27897 27920 19674 19824 23010 17118 17995 2...

NB. how many edges?

#~.,edges

895

NB. display part of one

</lang>

Image uploads [temporarily?] blocked; fall back to ascii art:

((284035&=)" 0 (80 {. 375 }. edges)){' #'

### ## ...

# ...

## ...

### ...

## ...

### ...

#### ...

### ...

## ...

#### ...

### ...

## ...

### ...

#### ...

## ...

### ...

#### ...

### ...

## ...

### ...

## ...

### ...

#### ...

## ...

### ...

#### ...

### ...

## ...

####### ...

#### ...

##### ...

### ...

#### ...

### ...

#### ...

### ...

## ...

##### ...

###### ...

### ...

## ...

#### ...

...

</lang>

=={{header|Mathematica}}==