Simple image filters using convolution matrix

Monkey Forums/Monkey Code/Simple image filters using convolution matrix

Beaker (Posted 2013) [#1]

Here is some nice code that can apply realtime (but sometimes slow) filters to images. Including blur, sharpen, emboss, edge detect, median blur, gaussian blur etc. The Median function is particularly slow. See an example here: Example Enjoy. If you make any improvements, please post them here. example.monkey 'Convolve image by Beaker 2013 Import mojo Import convmatrix Class ConvTest Extends App Field img:Image Field newImg:Image Field conv:ConvMatrix = ConvMatrix.GaussianBlur ' Field conv:ConvMatrix = ConvMatrix.Emboss ' Field conv:ConvMatrix = ConvMatrix.Blur ' Field conv:ConvMatrix = ConvMatrix.BlurMore ' Field conv:ConvMatrix = ConvMatrix.EdgeDetect ' Field conv:ConvMatrix = ConvMatrix.EdgeDetect2 ' Field conv:ConvMatrix = ConvMatrix.EdgeDetect3 ' Field conv:ConvMatrix = ConvMatrix.Sharpen Method OnCreate() SetUpdateRate(30) ' img = LoadImage("skull.png") img = LoadImage("original.jpg") End Method OnUpdate() End Method OnRender() If Not newImg newImg = CreateImage(img.Width(), img.Height()) Cls DrawImage img,0,0 Convolve(img, newImg, conv) ' Median(img, newImg, conv) 'img = newImg End Cls 0, 0, 0 DrawImage newImg,0,0 DrawImage img, img.Width(),0 DrawText "Tap SPACE to apply filter again", 320,390,0.5,0.5 If KeyDown(KEY_SPACE) Convolve(img, newImg, conv) ' Median(img, newImg, conv) img = newImg End End End Function Main() New ConvTest End convmatrix.monkey 'Convolution Matrix by Beaker 2013 Strict Import mojo Class ConvMatrix Field matrix:Float[9] Field factor:Float = 1 Field offset:Float = 0 Field size:Int = 3 Method New(factor:Float=1, offset:Float=0) Self.factor = factor Self.offset = offset End Method New(mat:Float[], factor:Float=1, offset:Float=0) Self.matrix = mat Self.factor = factor Self.offset = offset End Method SetAll:Void(val:Float) For Local i:= 0 To 8 matrix[i] = val End End Function Blur:ConvMatrix() Local conv:ConvMatrix = New ConvMatrix() conv.SetAll(1) Return conv End Function BlurMore:ConvMatrix() Local conv:ConvMatrix = New ConvMatrix([1.0,2.0,1.0, 2.0,4.0,2.0, 1.0,2.0,1.0], 1,0) Return conv End Function Emboss:ConvMatrix() Local conv:ConvMatrix = New ConvMatrix([-2.0,-1.0,0.0, -1.0,1.0,1.0, 0.0,1.0,2.0], 1,127) Return conv End Function GaussianBlur:ConvMatrix() Local conv:ConvMatrix = New ConvMatrix() conv.matrix = [ 0.0,0.0,0.0,5.0,0.0,0.0,0.0, 0.0,5.0,18.0,32.0,18.0,5.0,0.0, 0.0,18.0,64.0,100.0,64.0,18.0,0.0, 5.0,32.0,100.0,100.0,100.0,32.0,5.0, 0.0,18.0,64.0,100.0,64.0,18.0,0.0, 0.0,5.0,18.0,32.0,18.0,5.0,0.0, 0.0,0.0,0.0,5.0,0.0,0.0,0.0] 'Print Sqrt(conv.matrix.Length) conv.size = Sqrt(conv.matrix.Length) 'should be 7 Return conv End Function EdgeDetect:ConvMatrix() Local conv:ConvMatrix = New ConvMatrix([-1.0,-1.0,-1.0, -1.0,8.0,-1.0, -1.0,-1.0,-1.0], 1,0) Return conv End Function EdgeDetect2:ConvMatrix() Local conv:ConvMatrix = New ConvMatrix([-5.0,0.0,0.0, 0.0,0.0,0.0, 0.0,0.0,5.0], 1,0) Return conv End Function EdgeDetect3:ConvMatrix() Local conv:ConvMatrix = New ConvMatrix([1.0,1.0,1.0, 1.0,-7.0,1.0, 1.0,1.0,1.0], 1,0) Return conv End Function Sharpen:ConvMatrix() Local conv:ConvMatrix = New ConvMatrix([-1.0,-1.0,-1.0, -1.0,9.0,-1.0, -1.0,-1.0,-1.0], 1,0) Return conv End End Function Convolve:Bool(image:Image, newImage:Image, conv:ConvMatrix) If conv.factor = 0 Return False Local rgb:Int Local r:Int, g:Int, b:Int Local divisor:Float = 0 Local halfSize:Int = Floor(Float(conv.size)/2.0) ' Print "halfSize="+halfSize Local pixels:Int[] = New Int[image.Width()*image.Height()] Local newPixels:Int[] = New Int[image.Width()*image.Height()] ReadPixels(pixels, 0,0, image.Width(), image.Height()) ' Print pixels.Length+" "+image.Width()+" "+image.Height() For Local x2:Int = 0 Until conv.size For Local y2:Int = 0 Until conv.size divisor += conv.matrix[x2+y2*conv.size] End End For Local x:Int = halfSize Until image.Width()-halfSize For Local y:Int = halfSize Until image.Height()-halfSize 'Print x+" "+y Local newr:Int = 0 Local newg:Int = 0 Local newb:Int = 0 For Local x2:Int = -halfSize To halfSize For Local y2:Int = -halfSize To halfSize 'Print (x+x2)*image.Height()+(y+y2) rgb = pixels[(x+x2)+(y+y2)*image.Width()] r = (rgb Shr 16) & $ff g = (rgb Shr 8) & $ff b = rgb & $ff Local offset:Int = (x2+halfSize)+(y2+halfSize)*conv.size newr += Float(r) * conv.matrix[offset] newg += Float(g) * conv.matrix[offset] newb += Float(b) * conv.matrix[offset] End End If divisor = 0 divisor = 1 newr /= divisor newg /= divisor newb /= divisor newr += conv.offset newg += conv.offset newb += conv.offset newr = Min(Max(newr,0),255) newg = Min(Max(newg,0),255) newb = Min(Max(newb,0),255) newPixels[x+y*image.Width()] = $ff000000 | (newr Shl 16) | (newg Shl 8) | newb End End newImage.WritePixels(newPixels, 0,0, image.Width(), image.Height()) Return True End Function Median:Bool(image:Image, newImage:Image, conv:ConvMatrix) If conv.factor = 0 Return False Local rgb:Int Local r:Int, g:Int, b:Int Local halfSize:Int = Floor(Float(conv.size)/2.0) ' Print "halfSize="+halfSize Local pixels:Int[] = New Int[image.Width()*image.Height()] Local newPixels:Int[] = New Int[image.Width()*image.Height()] ReadPixels(pixels, 0,0, image.Width(), image.Height()) ' Print pixels.Length+" "+image.Width()+" "+image.Height() Local newr:Int = 0 Local newg:Int = 0 Local newb:Int = 0 For Local x:Int = halfSize Until image.Width()-halfSize For Local y:Int = halfSize Until image.Height()-halfSize 'Print x+" "+y Local rList:= New FloatList Local gList:= New FloatList Local bList:= New FloatList For Local x2:Int = -halfSize To halfSize For Local y2:Int = -halfSize To halfSize 'Print (x+x2)*image.Height()+(y+y2) rgb = pixels[(x+x2)+(y+y2)*image.Width()] r = (rgb Shr 16) & $ff g = (rgb Shr 8) & $ff b = rgb & $ff rList.AddLast(r) gList.AddLast(g) bList.AddLast(b) End End rList.Sort() gList.Sort() bList.Sort() Local rArr:= rList.ToArray() Local gArr:= gList.ToArray() Local bArr:= bList.ToArray() If rArr.Length Mod 2 = 1 newr = rArr[rArr.Length/2] newg = gArr[gArr.Length/2] newb = bArr[bArr.Length/2] Else newr = (rArr[rArr.Length/2] + rArr[rArr.Length/2+1]) /2 newg = (gArr[gArr.Length/2] + gArr[gArr.Length/2+1]) /2 newb = (bArr[bArr.Length/2] + bArr[gArr.Length/2+1]) /2 End newPixels[x+y*image.Width()] = $ff000000 | (newr Shl 16) | (newg Shl 8) | newb End End newImage.WritePixels(newPixels, 0,0, image.Width(), image.Height()) Return True End

Beaker (Posted 2013) [#2]

I forgot to mention that it currently doesn't handle image edges very elegantly. I will probably fix this at some point.

semar (Posted 2013) [#3]

Nice !

Difference (Posted 2013) [#4]

2x Nice !

Gerry Quinn (Posted 2013) [#5]

What should one do with edges? I'm thinking two options: average the colour near an edge and treat outside pixels as being that colour, or wrap around (useful for tiled graphics).

slenkar (Posted 2013) [#6]

gimp offers a choice for tiled/nontiled this opens the possibility for monkey to do an elite style game with procedurally generated planet images ^_^

muddy_shoes (Posted 2013) [#7]

I've done a little tweaking to improve performance a bit. The speed-up ranges from a little to a lot depending on target and build settings. I only tried HTML5, Flash, XNA and GLFW but the techniques are mostly transferable. Going native with this sort of thing would be the natural end-game though. The output may not be exactly the same as the original but it looks visually equivalent. 'This defines whether the colour channels are split into arrays first. 'Whether this is useful or not mostly depends on the cost of accessing array elements. 'For the most part turning it off is better or no worse than on. #SEPARATE_CHANNELS = "False" Function Convolve2:Bool(image:Image, newImage:Image, conv:ConvMatrix) If conv.factor = 0 Return False 'store values locally to avoid call/reference costs Local imgWidth:Int = image.Width() Local imgHeight:Int = image.Height() Local convSize:Int = conv.size Local convMatLength:Int = conv.matrix.Length() Local convOffset:Int = conv.offset Local divisor:Float = 0 Local halfSize:Int = Floor(Float(convSize) / 2.0) Local numPixels:Int = imgWidth * imgHeight Local pixels:Int[] = New Int[numPixels] ReadPixels(pixels, 0, 0, imgWidth, imgHeight) #If SEPARATE_CHANNELS = "True" 'separate the colour channels Local rPixels:Int[] = New Int[numPixels] Local gPixels:Int[] = New Int[numPixels] Local bPixels:Int[] = New Int[numPixels] For Local pixIndex:Int = 0 Until numPixels Local rgb:Int = pixels[pixIndex] rPixels[pixIndex] = (rgb Shr 16) & $ff gPixels[pixIndex] = (rgb Shr 8) & $ff bPixels[pixIndex] = rgb & $ff End 'no need for second buffer Local newPixels:Int[] = pixels #Else Local newPixels:Int[] = New Int[numPixels] #End Local matrix:Float[] = New Float[convMatLength] For Local i:Int = 0 Until convMatLength divisor += conv.matrix[i] End If divisor = 0 divisor = 1 End 'The divisor seems to be just used to normalise the result, so normalise the matrix instead divisor = 1.0 / divisor For Local i:Int = 0 Until convMatLength matrix[i] = conv.matrix[i] * divisor End For Local x:Int = halfSize Until imgWidth - halfSize For Local y:Int = halfSize Until imgHeight-halfSize Local r:Int, g:Int, b:Int Local newr:Float = convOffset Local newg:Float = convOffset Local newb:Float = convOffset Local pixIndex:Int = x - halfSize + (y - halfSize) * imgWidth Local matIndex:Int = 0 For Local y2:Int = -halfSize To halfSize For Local x2:Int = -halfSize To halfSize #If SEPARATE_CHANNELS = "True" r = rPixels[pixIndex] g = gPixels[pixIndex] b = bPixels[pixIndex] #Else Local rgb:Int = pixels[pixIndex] r = (rgb Shr 16) & $ff g = (rgb Shr 8) & $ff b = rgb & $ff #End Local convVal:Float = matrix[matIndex] newr += r * convVal newg += g * convVal newb += b * convVal matIndex += 1 pixIndex += 1 End pixIndex += imgWidth - convSize End r = Clamp(Int(newr), 0, 255) g = Clamp(Int(newg), 0, 255) b = Clamp(Int(newb), 0, 255) newPixels[x + y * imgWidth] = $ff000000 | (r Shl 16) | (g Shl 8) | b End End newImage.WritePixels(newPixels, 0,0, imgWidth, imgHeight) Return True End Function Swap:Void(arr:Int[], a:Int, b:Int) Local tmp:Int = arr[a] arr[a] = arr[b] arr[b] = tmp End 'QuickSelect. Not tested much. Based on psuedocode from <a href="http://en.wikipedia.org/wiki/Selection_algorithm" target="_blank">http://en.wikipedia.org/wiki/Selection_algorithm</a> Function Partition:Int(arr:Int[], left:Int, right:Int, pivotIndex:Int) Local pivotValue:Int = arr[pivotIndex] Swap(arr, pivotIndex, right) ' Move pivot to end Local storeIndex:Int = left For Local i:Int = left Until right If arr[i] <= pivotValue Swap(arr, storeIndex, i) storeIndex += 1 End End Swap(arr, right, storeIndex) ' Move pivot To its final place Return storeIndex End Function SelectVal:Int(arr:Int[], left:Int, right:Int, k:Int) While True ' select pivotIndex between left and right Local pivotIndex:Int = Int(Rnd(left, right)) Local pivotNewIndex:Int = Partition(arr, left, right, pivotIndex) Local pivotDist:Int = pivotNewIndex - left + 1 If pivotDist = k Return arr[pivotNewIndex] ElseIf k < pivotDist right = pivotNewIndex - 1 Else k = k - pivotDist left = pivotNewIndex + 1 End End End Function Median2:Bool(image:Image, newImage:Image, conv:ConvMatrix) Local imgWidth:Int = image.Width() Local imgHeight:Int = image.Height() Local convSize:Int = conv.size If conv.factor = 0 Return False Local halfSize:Int = Floor(Float(convSize) / 2.0) Local numPixels:Int = imgWidth * imgHeight Local pixels:Int[] = New Int[numPixels] ReadPixels(pixels, 0, 0, imgWidth, imgHeight) Local newr:Int = 0 Local newg:Int = 0 Local newb:Int = 0 Local convMatLength:Int = conv.matrix.Length() Local arrMid:Int = (convMatLength + 1) * 0.5 Local rWindow:Int[] = New Int[convMatLength] Local gWindow:Int[] = New Int[convMatLength] Local bWindow:Int[] = New Int[convMatLength] #If SEPARATE_CHANNELS = "True" 'separate the colour channels Local rPixels:Int[] = New Int[numPixels] Local gPixels:Int[] = New Int[numPixels] Local bPixels:Int[] = New Int[numPixels] For Local pixIndex:Int = 0 Until numPixels Local rgb:Int = pixels[pixIndex] rPixels[pixIndex] = (rgb Shr 16) & $ff gPixels[pixIndex] = (rgb Shr 8) & $ff bPixels[pixIndex] = rgb & $ff End 'no need for second buffer Local newPixels:Int[] = pixels #Else Local newPixels:Int[] = New Int[numPixels] #End For Local x:Int = halfSize Until imgWidth-halfSize For Local y:Int = halfSize Until imgHeight - halfSize Local convIndex:Int = 0 For Local x2:Int = -halfSize To halfSize For Local y2:Int = -halfSize To halfSize Local pixIndex:Int = (x + x2) + (y + y2) * imgWidth #If SEPARATE_CHANNELS = "True" rWindow[convIndex] = rPixels[pixIndex] gWindow[convIndex] = gPixels[pixIndex] bWindow[convIndex] = bPixels[pixIndex] #Else Local rgb:Int = pixels[pixIndex] rWindow[convIndex] = (rgb Shr 16) & $ff gWindow[convIndex] = (rgb Shr 8) & $ff bWindow[convIndex] = rgb & $ff #End convIndex += 1 End End newr = SelectVal(rWindow, 0, convMatLength - 1, arrMid) newg = SelectVal(gWindow, 0, convMatLength - 1, arrMid) newb = SelectVal(bWindow, 0, convMatLength - 1, arrMid) newPixels[x + y * imgWidth] = $ff000000 | (newr Shl 16) | (newg Shl 8) | newb End End newImage.WritePixels(newPixels, 0, 0, imgWidth, imgHeight) Return True End

Beaker (Posted 2013) [#8]

The only problem (and a quite major one) that I can see with your nice optimised code is that it will be much harder (if not impossible) to adjust it to handle image edges. Or am I missing something?

muddy_shoes (Posted 2013) [#9]

You're missing a description of how you would handle edges.

Beaker (Posted 2013) [#10]

Like this: Code removed to protect the stupid (ie. me)

muddy_shoes (Posted 2013) [#11]

What's that meant to be doing? It looks like it wraps the pixel values to the right and bottom and repeats the border values to the left and top.

Beaker (Posted 2013) [#12]

It doesn't wrap them, instead it clamps the edges, which works great.

muddy_shoes (Posted 2013) [#13]

[monkeycode] For Local x2:Int = -halfSize To halfSize Local newx:Int = (x+x2) Mod image.Width() If newx < 0 newx = 0 For Local y2:Int = -halfSize To halfSize Local newy:Int = (y+y2) Mod image.Height() If newy < 0 newy = 0 [/monkeycode] If you put (x+x2) = width and (y+y2) = height into that you get 0,0 out. It wraps. If you put (x+x2) = -1 and (y+y2) = -1 into that you get 0,0 out. It clamps.

muddy_shoes (Posted 2013) [#14]

Anyway, I believe this does what you intend: 'This defines whether the colour channels are split into arrays first. 'Whether this is useful or not mostly depends on the cost of accessing array elements. 'For the most part turning it off is better or no worse than on. #SEPARATE_CHANNELS = "False" Function Convolve2:Bool(image:Image, newImage:Image, conv:ConvMatrix) If conv.factor = 0 Return False 'store values locally to avoid call/reference costs Local imgWidth:Int = image.Width() Local imgHeight:Int = image.Height() Local convSize:Int = conv.size Local convMatLength:Int = conv.matrix.Length() Local convOffset:Int = conv.offset Local divisor:Float = 0 Local halfSize:Int = Floor(Float(convSize) / 2.0) Local numPixels:Int = imgWidth * imgHeight Local pixels:Int[] = New Int[numPixels] ReadPixels(pixels, 0, 0, imgWidth, imgHeight) #If SEPARATE_CHANNELS = "True" 'separate the colour channels Local rPixels:Int[] = New Int[numPixels] Local gPixels:Int[] = New Int[numPixels] Local bPixels:Int[] = New Int[numPixels] For Local pixIndex:Int = 0 Until numPixels Local rgb:Int = pixels[pixIndex] rPixels[pixIndex] = (rgb Shr 16) & $ff gPixels[pixIndex] = (rgb Shr 8) & $ff bPixels[pixIndex] = rgb & $ff End 'no need for second buffer Local newPixels:Int[] = pixels #Else Local newPixels:Int[] = New Int[numPixels] #End Local matrix:Float[] = New Float[convMatLength] For Local i:Int = 0 Until convMatLength divisor += conv.matrix[i] End If divisor = 0 divisor = 1 End 'The divisor seems to be just used to normalise the result, so normalise the matrix instead divisor = 1.0 / divisor For Local i:Int = 0 Until convMatLength matrix[i] = conv.matrix[i] * divisor End For Local x:Int = 0 Until imgWidth For Local y:Int = 0 Until imgHeight Local r:Int, g:Int, b:Int Local newr:Float = convOffset Local newg:Float = convOffset Local newb:Float = convOffset Local pixIndex:Int '= x - halfSize + (y - halfSize) * imgWidth Local matIndex:Int = 0 For Local y2:Int = -halfSize To halfSize Local mappedY:Int = Clamp(y + y2, 0, imgHeight - 1) For Local x2:Int = -halfSize To halfSize Local mappedX:Int = Clamp(x + x2, 0, imgWidth - 1) pixIndex = mappedX+mappedY*imgWidth #If SEPARATE_CHANNELS = "True" r = rPixels[pixIndex] g = gPixels[pixIndex] b = bPixels[pixIndex] #Else Local rgb:Int = pixels[pixIndex] r = (rgb Shr 16) & $ff g = (rgb Shr 8) & $ff b = rgb & $ff #End Local convVal:Float = matrix[matIndex] newr += r * convVal newg += g * convVal newb += b * convVal matIndex += 1 End End r = Clamp(Int(newr), 0, 255) g = Clamp(Int(newg), 0, 255) b = Clamp(Int(newb), 0, 255) newPixels[x + y * imgWidth] = $ff000000 | (r Shl 16) | (g Shl 8) | b End End newImage.WritePixels(newPixels, 0,0, imgWidth, imgHeight) Return True End

Beaker (Posted 2013) [#15]

Oops. Sorry, I'm an idiot. In my defense it's been a very long day. How about this: Function Convolve:Bool(image:Image, newImage:Image, conv:ConvMatrix) If conv.factor = 0 Return False Local rgb:Int Local r:Int, g:Int, b:Int Local divisor:Float = 0 Local halfSize:Int = Floor(Float(conv.size)/2.0) Local pixels:Int[] = New Int[image.Width()*image.Height()] Local newPixels:Int[] = New Int[image.Width()*image.Height()] ReadPixels(pixels, 0,0, image.Width(),image.Height()) For Local x2:Int = 0 Until conv.size For Local y2:Int = 0 Until conv.size divisor += conv.matrix[x2+y2*conv.size] End End For Local x:Int = 0 Until image.Width() For Local y:Int = 0 Until image.Height() Local newr:Int = 0 Local newg:Int = 0 Local newb:Int = 0 For Local x2:Int = -halfSize To halfSize Local newx:Int = Clamp(x+x2,0,image.Width()-1) For Local y2:Int = -halfSize To halfSize Local newy:Int = Clamp(y+y2,0,image.Height()-1) rgb = pixels[newx+newy*image.Width()] r = (rgb Shr 16) & $ff g = (rgb Shr 8) & $ff b = rgb & $ff Local offset:Int = (x2+halfSize)+(y2+halfSize)*conv.size newr += Float(r) * conv.matrix[offset] newg += Float(g) * conv.matrix[offset] newb += Float(b) * conv.matrix[offset] End End If divisor = 0 divisor = 1 newr /= divisor newg /= divisor newb /= divisor newr += conv.offset newg += conv.offset newb += conv.offset newr = Clamp(newr,0,255) newg = Clamp(newg,0,255) newb = Clamp(newb,0,255) newPixels[x+y*image.Width()] = $ff000000 | (newr Shl 16) | (newg Shl 8) | newb End End newImage.WritePixels(newPixels, 0,0, image.Width(), image.Height()) Return True End

Beaker (Posted 2013) [#16]

muddy_shoes - looks great.

NoOdle (Posted 2013) [#17]

thank you for posting this, I have never heard of convolution matrices before, very interesting reading up on them and their uses. I saw this as an interesting programming challenge and decided to try writing my own now. After a few hours I managed to get mine working correctly, It's always easier implementing something when there is reference code to help! I believe I have a working Sobel edge filter although I need to read up on it some more to make sure, the output seems to match but it was a weird one. Is there a list or website showing kernel values or filter names that can be used with this method? I have about 14 so far, would be good to get a complete collection.