Return to 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.

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.

This is my first 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've been doing some testing and discovered (and have now fixed) a few logical bugs. I'm testing using two images where I know one is located inside the other (and have verified this using another algorithm) but it appears this code currently can not find matches, though it appears correct.

open System
open System.Drawing
open System.Drawing.Imaging
open System.Runtime.InteropServices
module ImageSearch = 
 let LoadBitmapIntoArray (pBitmap:Bitmap) =
 let tBitmapData = pBitmap.LockBits( Rectangle(Point.Empty, pBitmap.Size), 
 ImageLockMode.ReadOnly, 
 PixelFormat.Format24bppRgb ) 
 // Bitmap.Stride can be negative to indicate different orientation of the bitmap
 let tImageArrayLength = Math.Abs(tBitmapData.Stride) * pBitmap.Height
 let tImageDataArray = Array.zeroCreate<byte> tImageArrayLength
 
 // Marshal.Copy(tImageDataArray, 0, tBitmapData.Scan0, tImageArrayLength)
 Marshal.Copy(tBitmapData.Scan0, tImageDataArray, 0, tImageArrayLength)
 pBitmap.UnlockBits(tBitmapData)
 pBitmap.Width, tImageDataArray
 let Transform2D ( (pArrayWidth:int), (pArray:byte[]) ) = 
 let tHeight = pArray.Length / ( pArrayWidth * 3 ) // 3 bytes per RGB
 [|
 for tHeightIndex in 0 .. tHeight - 1 do
 let tStart = tHeightIndex * ( pArrayWidth * 3 - 1 )
 let tFinish = tStart + pArrayWidth * 3 - 1
 yield [| 
 for tWidthIndex in tStart .. 3 .. tFinish do
 yield ( pArray.[tWidthIndex]
 , pArray.[tWidthIndex + 1] 
 , pArray.[tWidthIndex + 2] )
 |]
 |]
 let SearchSubset (tSmallArray:(byte * byte * byte)[][]) (tLargeArray:(byte * byte * byte)[][]) (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
 tSmallHeightIndex <- tSmallHeightIndex + 1
 tMatch
 with
 | _ -> false
 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 <- 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
 tHeightIndex <- tHeightIndex + 1
 tMatch, tWidthIndex, tHeightIndex
 [<EntryPoint>]
 let main (args:string[]) = 
 
 use tSmallBitmap = new Bitmap("testimage2.bmp")
 use tLargeBitmap = new Bitmap("testimage1.bmp")
 let tSuccess, xCoord, yCoord = SearchBitmap tSmallBitmap tLargeBitmap
 // General plan for looping
 // - Split single array for small image into 2d array of arrays
 // - Split single array for large image into 2d array of arrays
 // - Iterate through each array in large array looking for first value from small array
 // - If first value is found, then check for complete row
 // - If row is complete then check for second row (and so on)
 // - Stop searching horizontally when remaining pixels are smaller than search image width
  // - Stop searching vertically when remaining pixels are smaller than search image height 
 // Must return from function
 0

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 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

open System
open System.Drawing
open System.Drawing.Imaging
open System.Runtime.InteropServices
module ImageSearch = 
 let LoadBitmapIntoArray (pBitmap:Bitmap) =
 let tBitmapData = pBitmap.LockBits( Rectangle(Point.Empty, pBitmap.Size), 
 ImageLockMode.ReadOnly, 
 PixelFormat.Format24bppRgb ) 
 // Bitmap.Stride can be negative to indicate different orientation of the bitmap
 let tImageArrayLength = Math.Abs(tBitmapData.Stride) * pBitmap.Height
 let tImageDataArray = Array.zeroCreate<byte> tImageArrayLength
 
 Marshal.Copy(tImageDataArray, 0, tBitmapData.Scan0, tImageArrayLength)
 pBitmap.UnlockBits(tBitmapData)
 pBitmap.Width, tImageDataArray
 let Transform2D ( (pArrayWidth:int), (pArray:byte[]) ) = 
 let tHeight = pArray.Length / ( pArrayWidth * 3 ) // 3 bytes per RGB
 [|
 for tHeightIndex in 0 .. tHeight - 1 do
 let tStart = tHeightIndex * pArrayWidth
 let tFinish = tStart + pArrayWidth - 1 
 yield [| 
 for tWidthIndex in tStart .. 3 .. tFinish do
 yield ( pArray.[tWidthIndex]
 , pArray.[tWidthIndex + 1] 
 , pArray.[tWidthIndex + 2] )
 |]
 |]
 let SearchSubset (tSmallArray:(byte * byte * byte)[][]) (tLargeArray:(byte * byte * byte)[][]) (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 ) && tMatch do
 while ( tSmallWidthIndex < tSmallWidth ) && tMatch do
 let tLargeCurrentValue = tLargeArray.[tHeightIndex + tSmallHeightIndex].[tWidthIndex + tSmallWidthIndex]
 let tSmallCurrentValue = tSmallArray.[tSmallHeightIndex].[tSmallWidthIndex]
 if tSmallCurrentValue = tLargeCurrentValue then
 tSmallHeightIndex <- tSmallHeightIndex + 1
 tSmallWidthIndex <- tSmallWidthIndex + 1 
 else
 tMatch <- false
 tMatch
 with
 | _ -> false
 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 && tMatch do
 while tWidthIndex < tSearchWidth && tMatch do
 let tCurrentValue = tLargeArray.[tHeightIndex].[tWidthIndex]
 let tFirstSmallPixel = tSmallArray.[0].[0]
 if tCurrentValue = tFirstSmallPixel then
 tMatch <- SearchSubset tSmallArray tLargeArray ( tHeightIndex, tWidthIndex )
 if tMatch then tContinue <- false
 else
 tHeightIndex <- tHeightIndex + 1
 tWidthIndex <- tWidthIndex + 1
 tMatch, tHeightIndex, tWidthIndex
 [<EntryPoint>]
 let main (args:string[]) = 
 
 let tSmallBitmap = new Bitmap("testimage1.jpg")
 let tLargeBitmap = new Bitmap("testimage2.jpg")
 let tSuccess, xCoord, yCoord = SearchBitmap tSmallBitmap tLargeBitmap
 // General plan for looping
 // - Split single array for small image into 2d array of arrays
 // - Split single array for large image into 2d array of arrays
 // - Iterate through each array in large array looking for first value from small array
 // - If first value is found, then check for complete row
 // - If row is complete then check for second row (and so on)
 // - Stop searching horizontally when remaining pixels are smaller than search image width
 // - Stop searching vertically when remaining pixels are smaller than search image height 
 // Must return from function
 0

I've been doing some testing and discovered (and have now fixed) a few logical bugs. I'm testing using two images where I know one is located inside the other (and have verified this using another algorithm) but it appears this code currently can not find matches, though it appears correct.

open System
open System.Drawing
open System.Drawing.Imaging
open System.Runtime.InteropServices
module ImageSearch = 
 let LoadBitmapIntoArray (pBitmap:Bitmap) =
 let tBitmapData = pBitmap.LockBits( Rectangle(Point.Empty, pBitmap.Size), 
 ImageLockMode.ReadOnly, 
 PixelFormat.Format24bppRgb ) 
 // Bitmap.Stride can be negative to indicate different orientation of the bitmap
 let tImageArrayLength = Math.Abs(tBitmapData.Stride) * pBitmap.Height
 let tImageDataArray = Array.zeroCreate<byte> tImageArrayLength
 
 // Marshal.Copy(tImageDataArray, 0, tBitmapData.Scan0, tImageArrayLength)
 Marshal.Copy(tBitmapData.Scan0, tImageDataArray, 0, tImageArrayLength)
 pBitmap.UnlockBits(tBitmapData)
 pBitmap.Width, tImageDataArray
 let Transform2D ( (pArrayWidth:int), (pArray:byte[]) ) = 
 let tHeight = pArray.Length / ( pArrayWidth * 3 ) // 3 bytes per RGB
 [|
 for tHeightIndex in 0 .. tHeight - 1 do
 let tStart = tHeightIndex * ( pArrayWidth * 3 - 1 )
 let tFinish = tStart + pArrayWidth * 3 - 1 
 yield [| 
 for tWidthIndex in tStart .. 3 .. tFinish do
 yield ( pArray.[tWidthIndex]
 , pArray.[tWidthIndex + 1] 
 , pArray.[tWidthIndex + 2] )
 |]
 |]
 let SearchSubset (tSmallArray:(byte * byte * byte)[][]) (tLargeArray:(byte * byte * byte)[][]) (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
 tSmallHeightIndex <- tSmallHeightIndex + 1

 tMatch
 with
 | _ -> false
 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 <- 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
  tHeightIndex <- tHeightIndex + 1
 tMatch, tWidthIndex, tHeightIndex
 [<EntryPoint>]
 let main (args:string[]) = 
 
 use tSmallBitmap = new Bitmap("testimage2.bmp")
 use tLargeBitmap = new Bitmap("testimage1.bmp")
 let tSuccess, xCoord, yCoord = SearchBitmap tSmallBitmap tLargeBitmap
 // General plan for looping
 // - Split single array for small image into 2d array of arrays
 // - Split single array for large image into 2d array of arrays
 // - Iterate through each array in large array looking for first value from small array
 // - If first value is found, then check for complete row
 // - If row is complete then check for second row (and so on)
 // - Stop searching horizontally when remaining pixels are smaller than search image width
 // - Stop searching vertically when remaining pixels are smaller than search image height 
 // Must return from function
 0