Получить позицию одного изображения в другом изображении

Question

У меня есть скриншот моего браузера, который отображает веб-сайт. Теперь я хочу узнать, где находится веб-сайт (viewport) (относительно всего снимка экрана). Как видно в виде прямоугольника с черной рамкой в ​​этом изображении:

У меня есть возможность добавить что-либо к DOM веб-сайта, прежде чем начать обработку изображения.

Я уже пытался генерировать QR-код, добавил его в верхнем левом и нижнем правом углу окна просмотра, а затем использовали ImageMagick для того, чтобы определить положение QR-код в большом изображении:

compare -metric "rmse" -subimage-search -dissimilarity-threshold "0.1" -virtual-pixel "edge" "haystack.png" "needle.png" "results.png" 

Однако это длится долгое время. Фактически, я ушел после 40 минут.

Я использовал QR-код, потому что, используя временную метку, я могу быть абсолютно уверен, что этот фрагмент изображения не будет найден нигде на веб-сайте.

Кроме того, размер QR-кода на скриншоте был вдвое больше размера исходного QR-кода, но я предполагаю, что это связано с тем, что мой Mac-экран имеет 144dpi.

Я использую node.js так что мне нужно либо что-то, что может быть выполнено с помощью командной строки (например, ImageMagick), так что я могу просто запустить его из узла или модуля прямого узла.

У меня есть то преимущество, что я могу выбрать, какое изображение я хочу найти на большом изображении. Я думаю, что точное знание того, что должно быть найдено, может быть полезной информацией для ускорения процесса (но я еще не знаю, как использовать эту информацию).

Answer 1

У меня есть несколько советов, которые вы можете рассмотреть для ускорения поиска, если вы находите поиск в субизаре слишком медленно.

1. Уменьшение размера изображения

я провел небольшой эксперимент, чтобы проверить в поисках разного размера игл разного размера стога, как это:

#!/bin/bash 

# Create a range of haystack sizes 
for h in 200 400 800; do 
    # And a range of needle sizes 
    for n in 10 20 40; do 
     # Create haystack to search in, containing two needles 
     convert -size ${h}x${h}! gradient:red-black -fill white \ 
       -draw "rectangle 100,100 139,139"    \ 
       -draw "rectangle 150,150 189,189"    \ 
       haystack.png 
     # Create a needle this size to search for 
     convert -size ${n}x${n}! xc:white needle.png 

     cp haystack.png haystack_${h}x${h}.png 
     cp needle.png needle${n}x${n}.png 

     # Search, measuring the time 
     start=$SECONDS 
     compare -dissimilarity-threshold 1.0 -metric rmse -subimage-search haystack.png needle.png null: > /dev/null 2>&1 
     end=$SECONDS 
     ((elapsed=end-start)) 
     echo Haystack:${h}x${h}, needle:${n}x${n}, time:$elapsed 
    done 
done 

И нашли, как размеры влияют на время поиска, например:

Haystack:200x200, needle:10x10, time:2 
Haystack:200x200, needle:20x20, time:2 
Haystack:200x200, needle:40x40, time:2 
Haystack:400x400, needle:10x10, time:8 
Haystack:400x400, needle:20x20, time:8 
Haystack:400x400, needle:40x40, time:10 
Haystack:800x800, needle:10x10, time:33 
Haystack:800x800, needle:20x20, time:36 
Haystack:800x800, needle:40x40, time:47 

Как вы можете видеть, размеры изображений значительно отличаются е.

Вот три стога, различных размеров, каждый из которых содержат 2 белых "иглы ":

А вот" результата" изображений, где ImageMagick думает "иглы "расположены:

2. Прекратите Как можно скорее

Если добавить параметр -similarity-threshold и установить его в разумное значение, вы можете сделать поиск прекращается, как только первый хороший матч найден - как grep -m 1.

Установка его, как это сделает его остановиться на первом идеальный матч (ноль разница в схожести):

-similarity-threshold 0.0 

или установив его, как это сделает его остановиться на первом «очень хороший матч»

-similarity-threshold 0.05 

и настройка по умолчанию 1.0, который никогда не совпадает и, таким образом, приводит к тому, поиск продолжится в течение всего изображения.

Теперь я знаю, что вы хотите найти верхнюю и нижнюю часть экрана, которая два матчи и может показаться, что быстро найти только первый матч не использовать. Но Конфуций, он сказал «повернуть изображение» :-)

Таким образом, найти свой первый (т.е. сверху) матч, а затем повернуть изображение (и иглы) на 180 градусов и снова искать, но на этот раз вы поиск снизу и может снова остановиться в первом матче. (Поверните свой результат тоже.)

3. Используйте все те прекрасные сердечники, за которые вы заплатили - распараллелите!

Вы можете разделить изображение на части и выполнить поиск параллельно, чтобы воспользоваться всеми этими прекрасными ядрами Intel, за которые вы столько заплатили. Вы должны быть немного осторожны, чтобы наложить немного, чтобы ваша игла не оседлала границу, по которой вы срезаете, но вам нужно только добавить на ленту ширину вашей иглы в области поиска ... вот так

#!/bin/bash 

# Create a range of haystack sizes 
for h in 200 400 800; do 
    # And a range of needle sizes 
    for n in 10 20 40; do 
     # Create haystack to search in, containing two needles 
     convert -size ${h}x${h}! gradient:red-black -fill white \ 
       -draw "rectangle 100,100 139,139"    \ 
       -draw "rectangle 150,150 189,189"    \ 
       haystack.png 
     # Create a needle this size to search for 
     convert -size ${n}x${n}! xc:white needle.png 

     cp haystack.png haystack_${h}x${h}.png 
     cp needle.png needle${n}x${n}.png 

     # Search, measuring the time 
     start=$SECONDS 
     compare -dissimilarity-threshold 1.0 -metric rmse -subimage-search haystack.png needle.png null: > /dev/null 2>&1 
     end=$SECONDS 
     ((elapsed=end-start)) 
     echo Haystack:${h}x${h}, needle:${n}x${n}, time:$elapsed 

     ((a=h/2)) 
     ((b=h/2)) 
     ((c=a+n)) 
     ((d=b+n)) 
     ((e=a-n)) 
     ((f=b-n)) 
     # Measure time for parallel search, including dividing up image  
     start=$SECONDS 
     convert haystack.png -crop ${c}x${d}+0+0  +repage h1.png 
     convert haystack.png -crop ${a}x${b}+${a}+0 +repage h2.png 
     convert haystack.png -crop ${a}x${b}+0+${b} +repage h3.png 
     convert haystack.png -crop ${c}x${d}+${e}+${f} +repage h4.png 
     for p in 1 2 3 4; do 
     compare -dissimilarity-threshold 1.0 -metric rmse -subimage-search h${p}.png needle.png null: > /dev/null 2>&1 & 
     done 
     wait 
     end=$SECONDS 
     ((elapsed=end-start)) 
     echo Parallel Haystack:${h}x${h}, needle:${n}x${n}, time:$elapsed 
    done 
done 

И вы можете видеть параллельные времена почти 4x ускорен по сравнению с однопоточных раз:

Haystack:200x200, needle:10x10, time:2 
Parallel Haystack:200x200, needle:10x10, time:0 
Haystack:200x200, needle:20x20, time:2 
Parallel Haystack:200x200, needle:20x20, time:1 
Haystack:200x200, needle:40x40, time:2 
Parallel Haystack:200x200, needle:40x40, time:1 
Haystack:400x400, needle:10x10, time:8 
Parallel Haystack:400x400, needle:10x10, time:2 
Haystack:400x400, needle:20x20, time:8 
Parallel Haystack:400x400, needle:20x20, time:3 
Haystack:400x400, needle:40x40, time:10 
Parallel Haystack:400x400, needle:40x40, time:4 
Haystack:800x800, needle:10x10, time:33 
Parallel Haystack:800x800, needle:10x10, time:10 
Haystack:800x800, needle:20x20, time:36 
Parallel Haystack:800x800, needle:20x20, time:11 
Haystack:800x800, needle:40x40, time:47 
Parallel Haystack:800x800, needle:40x40, time:14