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

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