Locating a bitmap inside another (larger) bitmap with F#

Question

This is my firstish (heavily rewritten) go at the completed project that I've been working on with CodeReview assistance, so further advice is appreciated! See here, here and here for the past history of the project.

I strongly suspect there's a much more functional way to manage my loops, so assistance with that area especially is what I would like.

I have a separate set of unit tests (visible here) which confirm that this code works with my two sample image sets.

namespace MathAlgorithms
module ArrayFunctions = 
 // Generic because it makes testing easier, yay math
 let SearchSubset (tSmallArray:'a[][]) (tLargeArray:'a[][]) (pCoordinate:(int * int)) =
 let tSmallHeight = tSmallArray.Length
 let tSmallWidth = tSmallArray.[0].Length
 let tHeightIndex = fst pCoordinate
 let tWidthIndex = snd pCoordinate
 let mutable tSmallHeightIndex = 0
 let mutable tSmallWidthIndex = 0
 let mutable tMatch = true
 try 
 while ( tSmallHeightIndex < tSmallHeight - 1 ) && tMatch do
 while ( tSmallWidthIndex < tSmallWidth - 1 ) && tMatch do
 let tLargeCurrentValue = tLargeArray.[tHeightIndex + tSmallHeightIndex].[tWidthIndex + tSmallWidthIndex]
 let tSmallCurrentValue = tSmallArray.[tSmallHeightIndex].[tSmallWidthIndex]
 if tSmallCurrentValue = tLargeCurrentValue then
 tSmallWidthIndex <- tSmallWidthIndex + 1 
 else
 tMatch <- false
 tSmallWidthIndex <- 0
 tSmallHeightIndex <- tSmallHeightIndex + 1
 tMatch
 with
 | _ -> false
namespace FsharpImaging
open System
open System.Drawing
open System.Drawing.Imaging
open System.Runtime.InteropServices
open MathAlgorithms
module ImageFunctions = 
 let LoadBitmapIntoArray (pBitmap:Bitmap) =
 let tBitmapData = pBitmap.LockBits( Rectangle(Point.Empty, pBitmap.Size), 
 ImageLockMode.ReadOnly, 
 PixelFormat.Format24bppRgb ) 
 let tImageArrayLength = Math.Abs(tBitmapData.Stride) * pBitmap.Height
 let tImageDataArray = Array.zeroCreate<byte> tImageArrayLength
 Marshal.Copy(tBitmapData.Scan0, tImageDataArray, 0, tImageArrayLength)
 pBitmap.UnlockBits(tBitmapData)
 ( pBitmap.Width, pBitmap.Height, tBitmapData.Stride ), tImageDataArray
 // Notes:
 // Image pixel data is stored BGR ( blue green red )
 // Image data is padded to be divisible by 4 (int32 width)
 let Transform2D ( (pDimension:int*int*int), (pArray:byte[]) ) = 
 let tWidth, tHeight, tStride = pDimension
 [|
 for tHeightIndex in 0 .. ( tHeight - 1 ) do
 let tStart = tHeightIndex * tStride
 let tFinish = ( tStart + tWidth * 3 ) - 1
 yield [| 
 for tWidthIndex in tStart .. 3 .. tFinish do
 yield ( pArray.[tWidthIndex]
 , pArray.[tWidthIndex + 1] 
 , pArray.[tWidthIndex + 2] )
 |]
 |]
module ImageSearch = 
 open ImageFunctions
 let SearchBitmap (pSmallBitmap:Bitmap) (pLargeBitmap:Bitmap) = 
 let tSmallArray = Transform2D <| LoadBitmapIntoArray pSmallBitmap 
 let tLargeArray = Transform2D <| LoadBitmapIntoArray pLargeBitmap
 let tSearchWidth = pLargeBitmap.Width - pSmallBitmap.Width
 let tSearchHeight = pLargeBitmap.Height - pSmallBitmap.Height
 let mutable tHeightIndex = 0
 let mutable tWidthIndex = 0
 let mutable tMatch = false
 let mutable tContinue = true
 while ( tHeightIndex < tSearchHeight - 1 ) && tContinue do
 while ( tWidthIndex < tSearchWidth - 1 ) && tContinue do
 let tCurrentValue = tLargeArray.[tHeightIndex].[tWidthIndex]
 let tFirstSmallPixel = tSmallArray.[0].[0]
 if tCurrentValue = tFirstSmallPixel then
 tMatch <- ArrayFunctions.SearchSubset tSmallArray tLargeArray ( tHeightIndex, tWidthIndex )
 if tMatch then tContinue <- false
 if tMatch = false && tContinue = true then
 tWidthIndex <- tWidthIndex + 1
 if tMatch = false && tContinue = true then
 tWidthIndex <- 0 // Reset to search next row
 tHeightIndex <- tHeightIndex + 1
 tMatch, tWidthIndex, tHeightIndex
namespace MainProgram
open System.Drawing
open System.Drawing.Imaging
open System.Diagnostics
open FsharpImaging
module Main = 
 [<EntryPoint>]
 let main (args:string[]) = 
 use tSmallBitmap = new Bitmap("searchimage.bmp")
 use tLargeBitmap = new Bitmap("containingimage.bmp")
 let tSuccess, xCoord, yCoord = ImageSearch.SearchBitmap tSmallBitmap tLargeBitmap
 // Must return from function
 0

• Ken: Note: if somebody can show me how to change my while-do loop to be more F#-ish/functional, I will happily put a bounty on this question. =)
• Ken: Updated my OP to include new, fixed code. The program is in a working state now.

Answer 1

try ... with | _ -> false is bad. Like, very bad. The equivalent in C# is

try
{
 ...
}
catch (Exception)
{
 return false;
}

See this answer on SO for good advice on exception handling, and this one line in particular:

Only catch what you can handle and recover from.

In that particular code, the only exception I can imagine being thrown is an IndexOutOfRangeException, which you definitely want to know about. If it's thrown, it means your code is wrong.

---

I mentioned in a previous answer that Hungarian notation is dead and buried, and I feel that I'm not going to change your mind, but I will say it again just in case :) tImagine pIf tMy tReview pLooked tLike tThis...

---

You can use pattern matching to simplify this

let tHeightIndex = fst pCoordinate
let tWidthIndex = snd pCoordinate

to this

let heightIndex, widthIndex = coordinate

Or since coordinate is only used for these values, you can change the function signature to

let SearchSubset (smallArray : 'a[][]) (largeArray : 'a[][]) (heightIndex : int, widthIndex : int)

While we're looking at this, SearchSubset is a misleading name. I would suggest isSubmatrix.

---

I'm not sure, but it looks like you have off-by-one errors in these lines:

while ( tSmallHeightIndex < tSmallHeight - 1 ) && tMatch do
 while ( tSmallWidthIndex < tSmallWidth - 1 ) && tMatch do

I would think smallHeightIndex should range over [0, smallHeight), and similarly for smallWidthIndex.

---

Now as for the loops... I'm going to sidestep the entire issue by suggesting another way of writing this. F# has nice support for array slices and structural equality, which allows us to write the following:

let isSubmatrix (small : 'a[][]) (large : 'a[][]) (y : int, x : int) : bool =
 // TODO: bounds checking.
 let yMax = y + small.Length - 1
 let xMax = x + small.[0].Length - 1
 large.[y .. yMax] |> Array.map (fun row -> row.[x .. xMax]) = small

And some sample tests

let large = [| [| 0; 1; 2 |]
 ; [| 3; 4; 5 |]
 ; [| 6; 7; 8 |]
 ; [| 9; 10; 11 |] |]
printfn "%A" <| isSubmatrix [| [| 6; 7 |] ; [| 9 ; 10 |] |] large (2, 0)
printfn "%A" <| isSubmatrix [| [| 6; 7; 8 |] ; [| 9 ; 10; 11 |] |] large (2, 0)
printfn "%A" <| isSubmatrix [| [| 1 |] ; [| 4 |] |] large (0, 1)

OK, so what's going on here? Let's look at what the slices are doing.

large.[y .. yMax] will give us \$n\$ rows of large starting at row y, where \$n\$ is the number of rows in small.

Array.map (fun row -> row.[x .. xMax]) will then give us \$m\$ elements of each row, starting at column x, where \$m\$ is the number of columns in small.

For example,

printfn "%A" (large.[2 .. 3] |> Array.map (fun row -> row.[1 .. 2]))

will print

[|[|7; 8|]; [|10; 11|]|]

F# even supports slicing 2D arrays, which is nice:

let isSubmatrix (small : 'a[,]) (large : 'a[,]) (y : int, x : int) : bool =
 // TODO: bounds checking.
 let yMax = y + Array2D.length1 small - 1
 let xMax = x + Array2D.length2 small - 1
 large.[y .. yMax, x .. xMax] = small

• Ken: I'm still digesting your answer and advice. I'm sure I'll have questions later. =)
• Ken: You'll be happy to know that in my refactoring my code to use recursive loops rather than while-do loops, I've been stripping out my pseudo-hungarian notation. That style makes a lot of sense to me in more object oriented design, but it's starting to add more confusion than clarity for functional programming. =)
• Ken: Just a note, concerning the off by one error, I checked with and without the loop shortened by one, and I get an out-of-range-index error when I don't subtract one from my search range and domain. So I think it would indicate that the -1 is necessary. =)