Just a simple lib that uses in it the Nuod lib, a powerful Linear Algebra lib for Odin.
Find best patch matches in an image using FFT-based ZNCC. ZNCC - Zero-mean Normalized Cross-Correlation. It’s a similarity score used for template patch matching that’s much more robust than plain correlation when brightness / contrast changes. Scale / rotation are handled by trying each scale + angle and keeping global top_k.
scales or angles_ad can be empty -> treated as [ 1.0 ] and [ 0.0 ].
API:
find_similar_patches_fft :: proc (
img : [ ]f64,
img_w : int,
img_h : int,
patch : [ ]f64,
patch_w : int,
patch_h : int,
scales : [ ]f64,
angles_rad : [ ]f64,
top_k : int = 10,
min_score : f64 = 0.5,
allocator := context.allocator ) ->
( res_matches : [ ]Match,
ok : bool )
There is a single threaded version ( that uses less memory ) and a multi-threaded version ( that uses more memory but is several times faster ). If you want to paralelize but use less memory, reduce the number of thread. The memory usage depends on also on the resolution of the image.
The main file is just a demo for the lib find_patch_match
find_similar_patches_fft( )
Summary:
1. Creates a synthetic RGB image.
2. Converts to grayscale ( [ ]f64 ) .
3. Overlays 10 rotated + scaled copies of a letter template.
4. Runs FFT-based ( Z )NCC matching over a grid of scales / angles.
ZNCC - Zero-mean Normalized Cross-Correlation.
It’s a similarity score used for template/patch
matching that’s much more robust than plain correlation
when brightness / contrast changes.
5. Applies a simple NMS and prints the best 10 detections.
6. Writes a PPM so you can visually inspect the result.
>time ./find_match.exe
Ground truth placements:
#0: x=160 y=94 w=177 h=177 scale=3.893 ang=0.849
#1: x=384 y=36 w=59 h=59 scale=1.449 ang=-0.334
#2: x=655 y=830 w=61 h=61 scale=1.595 ang=0.220
#3: x=20 y=413 w=48 h=48 scale=1.076 ang=0.691
#4: x=514 y=778 w=120 h=120 scale=2.656 ang=0.690
#5: x=411 y=187 w=93 h=93 scale=2.190 ang=-0.408
#6: x=924 y=41 w=83 h=83 scale=2.213 ang=-0.182
#7: x=645 y=210 w=37 h=37 scale=0.840 ang=-0.501
#8: x=681 y=192 w=81 h=81 scale=2.088 ang=-0.227
#9: x=580 y=578 w=138 h=138 scale=3.890 ang=0.119
Top detections ( after simple NMS ):
#0: x=164 y=97 w=170 h=170 score=0.9539 scale=3.750 ang=0.830
#1: x=580 y=577 w=138 h=138 score=0.9419 scale=3.750 ang=0.160
#2: x=924 y=41 w=83 h=83 score=0.9338 scale=2.250 ang=-0.160
#3: x=518 y=781 w=113 h=113 score=0.9108 scale=2.500 ang=0.660
#4: x=22 y=414 w=45 h=45 score=0.8936 scale=1.000 ang=0.660
#5: x=685 y=195 w=74 h=74 score=0.8917 scale=2.000 ang=-0.160
#6: x=657 y=832 w=56 h=56 score=0.8785 scale=1.500 ang=0.160
#7: x=383 y=36 w=61 h=61 score=0.8289 scale=1.500 ang=-0.330
#8: x=416 y=192 w=82 h=82 score=0.8142 scale=2.000 ang=-0.330
Wrote nuod_find_patch_match.ppm ( view with any image viewer
that supports PPM, example: nomacs on Linux ).
real 0m41.615s
user 13m48.725s
sys 1m5.297s
MIT Open Source License
This lib uses Nuod lib as the linear algebra package. The nuod diretory is from the nuod library.
- Nuod ( Numerical Odin ) is an Odin package for creating, manipulating, and performing numerical operations on multi-dimensional arrays. It is inspired by the Numpy Python library.
https://github.com/Omair-R/Nuod
See the Nuod license on its site.
Best regards,
Joao Carvalho