1

Тема: Простенький алгоритм для порівняння картинок

Нарешті добравсі до написання коду на тому Nim'і. Скажу відразу — воно не набагато легше за C, але суть не в тому..
Якщо пам'ятаєте, то коли я вперше писав програмку для порівняння картинок, то я використовував алгоритм, котрий просто зменшував їх до розміру 64x64, потім робив всі пікселі чорно-білими (мається на увазі, що всі компоненти пікселя були однакові, в діапазоні від 0 до 255, а не просто чорні, або білі), ну а потім відбувалось порівняння кожного пікселя першої картинки з відповідним пікселем іншої, і підраховувалась кількість відмінних пікселів, якщо такі були — одже картинки не є ідентичними.
Далі я експериментував з картинками, котрі лише незначною мірою відрізняються, наприклад, якщо намалювати невеличку рисочку на одній з картинок, тоді кількість відмінних пікселів була не дуже великою, і таку картинку можна було б позначити, як потенційно такою ж самою, і тоді користувач сам повинен був би визначити, що з нею робити, залишати, чи ні.

Але я не передбачив одного випадку, коли кількість відмінних пікселів досить значна, хоча картинки практично ідентичні...
Сталося це от як...
Я відкрив картинку в GIMP'і, та затер декілька маленьких пташок у верхньому правому куті картинки. Якщо не дуже приглядатись, то цієї зміни навіть не видно було б. Потім я зберіг картинку, але при збереженні GIMP попросив мене обрати якість цієї картинки, вона була встановлена в 90%, і я її такою і залишив.

Після збереження картинки та порівняння її з оригіналом, виявилось, що 1017 пікселів з 4096 були різними!!!
А так трапилось, тому що оте налаштування якості картинки трішечки змінило чимало пікселів. Оку важко помітити різницю між 134 та 136, але програмка це бачить, та рахує такі пікселі як різні.

Виникає питання — як тоді розкермувати подібну ситуацію, адже очевидно, що ми не можемо використовувати коефіцієнт різних пікселів для того, аби судити, на скільки картинки є різними, бо в цьому випадку коефіцієнт буде аж 1017/4096 = ~0.25%, тобто, картинки різні на 25%, хоча це зовсім не так.

Далі виникає думка — а що, якщо брати до уваги "силу" різності між двома різними пікселями, тобто, рахувати відмінність усіх пікселів, замість того, аби рахувати кількість відмінних пікселів. В моєму випадку ця сума була лише 3012, вона досить мала, в порівнянні з сумою відмінностей між дійсно різними картинками — 341245.

Тоді можна взяти число, котре б представляло максимальну відмінність картинок, та ділити його на нашу суму відмінностей, цей коефіцієнт показуватиме вже хоч щось, але яке число використати як максимально можливу відмінність?

Якщо кожен піксель має значення від 0 до 255, і таких пікселів 4096, то може треба просто помножити 255 на 4096, а це буде 1044480, і тоді для першої пари картинок відмінність буде 3012 / 1044480 = ~0.003 що є дуже мало, враховуючи, що максимальний коефіцієнт буде 1. Тоді для другої пари картинок, котрі вже дійсно різні, цей коефіцієнт сягатиме 341245 / 1044480 = 0.32, а це вже дійсно чимало.

Подібний підрахунок відмінностей видається досить непоганим, але він працює лише для таких відмінностей, що рівномірно розподілені по картинці, але якщо відмінності зустрічаються в деяких конкретних місцях картинки, то загальна сума відмінностей може бути не дуже великою, але людське око точно помітить це (як вважаєте?).

Було б непогано, аби алгоритм розумів, коли відмінності є скупченими в одному, або декількох місцях, а коли вони рівномірно розподілені.

2

Re: Простенький алгоритм для порівняння картинок

Я тут ось думав про такий алгоритм, і як він може працювати. І перше, що приходить на думку - це обрахування відстані між пікселями, або ж розподілення картинки на, скажімо, чотири рівних сектори, а потім рахувати, який відсоток з усіх відмінних пікселів знаходиться в кожному з них, і якщо виходить так, що в одному секторі, наприклад, 80% усіх відмінних пікселів, то це означатиме, що в тому місці може бути щось домальоване.

Ідея в тому, аби алгоритм розумів, коли ми маємо дві ідентичні картинки, але одна з них просто відредагована. Але от мені здається, що для мого завдання це вже буде занадто, і це вже не буде "простим алгоритмом".

Також, поки писав, то пригадав, що мені траплялись дві майже ідентичні картинки, але одна з них має дещо приглушені кольори. Мабуть, якщо порівняти чорнобілі версії таких картинок, то відмінність між усіма пікселями буде однаковою, ось це теж треба взяти до уваги.
Але як це обрахувати? Можливо, варто рахувати відмінність між відмінностями пікселів? Адже якщо відмінність між усіма пікселями однакова, то тоді відмінність відмінностей буде 0.

3

Re: Простенький алгоритм для порівняння картинок

Досить складна тема щоб заново вигадувати велосипед, можливо краще взяти якийсь існуючий. OpenCV Homography

Подякували: 0xDADA11C7, koala, Chemist-i, FakiNyan, leofun015

4

Re: Простенький алгоритм для порівняння картинок

Arete написав:

Досить складна тема щоб заново вигадувати велосипед, можливо краще взяти якийсь існуючий. OpenCV Homography

то все дуже цікаво, але тоді моя проста програмка знову перестане бути простою

5

Re: Простенький алгоритм для порівняння картинок

Погляньте на задачу з іншого боку: Як ви оцінюєте на скільки різними є 2 зображення ?

Якби алгоритм був таким простим як ви хочете, то ви б не змогли тут писати.

Подякували: FakiNyan1

6

Re: Простенький алгоритм для порівняння картинок

Пане FakiNyan, ви вже обирайте - вам просто і неправильно чи складно і правильно. Одночасно тут не виходить, самі бачите.

Подякували: FakiNyan1

7

Re: Простенький алгоритм для порівняння картинок

та я вже завантажив книжку по комп'ютерному баченню :D
Nim має дуже застарілу бібліотеку opencv, як виявилось. Але в будь-якому випадку, це завдання не є частиною роботи, а просто гобі, тому час маю.

Подякували: 0xDADA11C71

8

Re: Простенький алгоритм для порівняння картинок

Просто не вийде бо треба буде, скоріш за все, використовувати перетворення: RGB -> HSV -> GREYSCALE

9

Re: Простенький алгоритм для порівняння картинок

Droid 77 написав:

Просто не вийде бо треба буде, скоріш за все, використовувати перетворення: RGB -> HSV -> GREYSCALE

шо? нашо? в мене там є вбудований фільтр greyscale

import imageman
import os

const maxDiff = 1044480

proc maxConstrast(image: var Image): void =
  var sum: int
  for p in image.data.mitems:
    sum += cast[int](p.r)
  let avarage = cast[uint8](toInt(sum / image.data.high))
  echo avarage
  for p in 0..image.data.high:
    var value = image[p][0]
    if value < avarage:
      value = 0
    else:
      value = 255
    for i in 0..2:
      image[p][i] = value 

proc compare(img1, img2: var Image): int {.discardable.} =
  var diff = 0
  var amountOfPixels = 0
  for p in 0..img1.data.high:
   let tempDiff = abs(cast[int](img1[p][0]) - cast[int](img2[p][0]))
   if tempDiff > 0:
     inc(amountOfPixels)
     diff+=tempDiff
  result = toInt(100 * diff / maxDiff)
  echo "diff: " & $(diff) & ", pixels: " & $(amountOfPixels)

let params = commandLineParams()

if params.len < 2:
  echo "Please choose 2 images"
  quit(QuitFailure)

var path1 = params[0]
var path2 = params[1]

# var p = initOptParser("file1 file2")
# while true:
#   p.next()
#   case p.kind
#   of cmdEnd: break
#   of cmdLongOption, cmdShortOption:
#     continue
#   of cmdArgument:
#     echo "Argument: ", p.key, p.value

var img = loadImage[ColorRGBU](path1)
var img1 = loadImage[ColorRGBU](path2)
img.filterGreyscale()
img = img.resizedBicubic(64, 64)
img1.filterGreyscale()
img1 = img1.resizedBicubic(64, 64)

let similarity = compare(img, img1)
echo "Images are similar by " & $(100-similarity) & "%"

img.saveJPEG("changed.jpg")
img1.saveJPEG("changed1.jpg")

10

Re: Простенький алгоритм для порівняння картинок

Якщо бажається відділити каракулі від зображення, то скоріше за все прийдеться перетворювати зображення в HSV.
Інакше вважаю, буде велика похибка порівняння.

11

Re: Простенький алгоритм для порівняння картинок

Колись робив тг-бота, який виконував роль сигналізації, на бекенді була вроді php обгортка цієї CLI тулзи
https://imagemagick.org/script/compare.php
Тобто порівняння двох зображень, якщо великий відсоток відмінності, значить хтось в будинку є :D
Ну тоді про нейронні мережі і тому подібне мова не йшла.

12

Re: Простенький алгоритм для порівняння картинок

imagemagick, то дуже потужна шняга, але розібратись в усіх тих параметрах аж капець як важко
але мені треба не просто порівняння кольорів, а порівняння форм, та їх розміщень, бо, наприклад, одна й та сама картинка, але пропущена через різні фільтри, для компа буде виглядати інакшою, але для людського ока буде очевидним, що це те саме, але перефарбоване

13 Востаннє редагувалося Droid 77 (24.10.2020 20:17:38)

Re: Простенький алгоритм для порівняння картинок

Так я це і маю на увазі.
Коли перетворили в hsv а після в greyscale, тоді простіше відділити зображення від сміття.
У свій час таке виробляв, в вигляді хоббійних інтересів, за допомогою бібліотеки OpenCV при дослідженнях стереоскопічного машинного зору.

14

Re: Простенький алгоритм для порівняння картинок

Droid 77 написав:

Так я це і маю на увазі.
Коли перетворили в hsv а після в greyscale, тоді простіше відділити зображення від сміття.
У свій час таке виробляв, в вигляді хоббійних інтересів, за допомогою бібліотеки OpenCV при дослідженнях стереоскопічного машинного зору.

та мені до того ще дійти треба, я не в темі...

15

Re: Простенький алгоритм для порівняння картинок

То можемо доходити до цього разом, не облишив цей інтерес що до машинного зору..
Тільки це все робив на плюсах, з пітоном в мене не склалося.. Не сподобались його правила: відступ вліво, відступ вправо, не та кількість спайсів - ти дурень.. :)

16

Re: Простенький алгоритм для порівняння картинок

так то не пайтон

17 Востаннє редагувалося Droid 77 (24.10.2020 21:17:58)

Re: Простенький алгоритм для порівняння картинок

Так а це..

import imageman
import os

з від-чого?

18

Re: Простенький алгоритм для порівняння картинок

запозичене може й з пайтона, але мова інша

19

Re: Простенький алгоритм для порівняння картинок

Яка саме?

20

Re: Простенький алгоритм для порівняння картинок

Nim жеж