Поиск совпадающих картинок - Страница 2

KumoKairo · 01.03.2013, 16:13

Могу предложить упрощенный способ проверки совпадения изображений по гистограмме. Поскольку слово WATERMARK написано черным цветом, то на гистограмме оно будет находиться в крайнем левом углу шириной максимум 10 яркости от абсолютно черной + вносить небольшие изменения в крайний правый край гистограммы, так как буквы залиты белым цветом.
Что делаем - берем два изображения, находим гистограммы по их битмапам через .histogram(); получаем два вектора гистограмм.
отрезаем немного от правой части от этих векторов (часть информации о буквах в крайней правой части, часть в крайней левой) Поскольку у букв белая заливка, то левый край вектора тоже будет затронут,его тоже нужно обрезать. Сравниваем две гистограммы. Центры гистограмм должны быть полностью идентичны
Останется только подобрать края отрезания правой и левой частей гистограммы, чтобы убирать всю информацию о черных буквах с белой заливкой

iflamberg · 01.03.2013, 16:15

Ребят, я просто не могу удержаться от вставки этой картинки, в ответ на пост Дипа. Прошу меня простить.

Цитата:

то изначально задать список характерных цветов на картинке

И что, ты будешь задавать список характерных цветов на картинке для каждой из 10000 изображений, как сказано у автора в задании? Вообще в курсе, что программа должна облегчать человеку жизнь и автоматизировать процессы, а не добавлять геморроя? Программно будешь определять характерные цвета? Основываясь на каком критерии?

Цитата:

чертим линию, допустим снизу, на коричневом цвете (если 1 пиксель коричневый, а 2 белый, то ищем в какой стороне есть коричневый).

А почему снизу? А если на картинке нет четко выделяемых контуров? Море сфотографированно и голубое небо. Квадрат малевича? Калейдоскоп? А как ищем в какой стороне коричневый? А если коричневый из нашего, почему-то выбранного априори, нижнего угла идет во все стороны, то куда мы рисуем линию?

Цитата:

Потом полученные конторы помещаем в специальный объект (он уже там идёт по координате x=0 и y=0). Эти конторы сравниваем по признакам: если углы у линий похожи, то вероятность "похожести" повышается".

Да ты что? А если просле распознования двух почти одинаковых картинок получились фигуры с разным количеством углов и точек? Из-за ватермарка.

Короче, Дип. На самом деле алгоритмы распознования изображений или проекты типа http://www.tineye.com/ именно так и устроенны. Но ты не представляешь себе, сколько там мелких "но" и сколько вещей необходимо учесть при программировании таких алгоритмов.

Так что, если картинки абсолютно одинаковые и отличаются только наличием ватермарка, то эту задачу лучше решить другим способом.

Hauts · 01.03.2013, 16:27

iflamberg, была б моя воля, — я б вас забанил.

iflamberg · 01.03.2013, 16:33

Почему? Я же попросил прощения. К тому же, это не просто "тупо"-пост, я объяснил Дипу, почему над его идеей надо еще поработать.

KumoKairo · 01.03.2013, 17:43

Пиу пиу, а у меня все работает =Р
Суть -пост №11

Код AS3:

package
{
	import flash.display.BitmapData;
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.display.Loader;
	import flash.net.URLRequest;
	import flash.display.LoaderInfo;
	import flash.display.Bitmap;
	import flash.filters.ColorMatrixFilter;
	import flash.geom.Point;
 
	/**
	 * ...
	 * @author Cyrill Nadezhdin
	 */
	public class Main extends Sprite
	{
		private var firstImage:BitmapData;
		private var secondImage:BitmapData;
		private var firstImageGrey:Vector.<Vector.<Number>>;
		private var secondImageGrey:Vector.<Vector.<Number>>;
 
		private var firstLoaded:Boolean = false;
		private var secondLoaded:Boolean = false;
 
		private var firstImagePath:String = "photo_1.jpg";
		private var secondImagePath:String = "photo_1_wm.jpg";
 
		//Верхняя граница обрезки гистограммы
		private var whiteThreshold:int = 0;
		//Нижняя граница обрезки гистограммы
		private var blackThreshold:int = 0;
		//Два массива, требуемые для применения черно-белого фильтра к картинке
		private var grayScale:Array = [0.3086, 0.3086, 0.3086, 0, 0, 0.3086, 0.3086, 0.3086, 0, 0, 0.3086, 0.3086, 0.3086, 0, 0, 0, 0, 0, 1, 0];
		private var filter:ColorMatrixFilter = new ColorMatrixFilter(grayScale);
		//Эпсилон, максимальное отклонение двух гистограмм, при котором считаем картинки одинаковыми
		private var epsilon:Number = 1000;
 
		//Просто загрузка файлов в лоб, не обращайте внимания
		public function Main():void
		{
			var loader1:Loader = new Loader();
			loader1.contentLoaderInfo.addEventListener(Event.COMPLETE, onFirstComplete);
			loader1.load(new URLRequest(firstImagePath));
 
			var loader2:Loader = new Loader();
			loader2.contentLoaderInfo.addEventListener(Event.COMPLETE, onSecondComplete);
			loader2.load(new URLRequest(secondImagePath));
		}
 
		private function onFirstComplete(e:Event):void
		{
			firstImage = Bitmap(LoaderInfo(e.target).content).bitmapData;
			//=================================================================
			//Делаем из картинки черно-белую, нас не интересуют цвета
			firstImage.applyFilter(firstImage, firstImage.rect, new Point(), filter);
			firstImageGrey = firstImage.histogram();
			//=================================================================
			firstLoaded = true;
			if (secondLoaded)
			{
				compare();
			}
		}
 
		private function onSecondComplete(e:Event):void
		{
			secondImage = Bitmap(LoaderInfo(e.target).content).bitmapData;
			//=================================================================
			//Делаем из картинки черно-белую, нас не интересуют цвета
			secondImage.applyFilter(secondImage, secondImage.rect, new Point(), filter);
			secondImageGrey = secondImage.histogram();
			//=================================================================
			secondLoaded = true;
			if (firstLoaded)
			{
				compare();
			}
		}
		private function compare():void
		{
			var splicedFirstHisto:Vector.<Number> = firstImageGrey[0];
			var splicedSecondHisto:Vector.<Number> = secondImageGrey[0];
 
			//Обрезаем гистограммы снизу. с яркости 0 до значения порога для черного цвета
			splicedFirstHisto.splice(0, blackThreshold);
			splicedSecondHisto.splice(0, blackThreshold);
			//Обрезаем гистограммы сверху. Последние n значений, определяемые порогом белого цвета
			splicedFirstHisto.splice(256 - whiteThreshold, 256 - whiteThreshold);
			splicedSecondHisto.splice(256 - whiteThreshold, 256 - whiteThreshold);
 
			//Находим разницу, сравнивая две гистограммы
			if (findDistinction(splicedFirstHisto, splicedSecondHisto) < epsilon)
			{
				trace("ЭТО ТЕ САМЫЕ КАРТИНКИ УРУРУ");
			}
			else
			{
				trace("Разные совсем");
			}
 
		}
		private function findDistinction(vectorA:Vector.<Number>, vectorB:Vector.<Number>):Number
		{
			var dist:Number = 0;
			for (var i:uint = 0; i < vectorA.length; i++)
			{
				dist += Math.sqrt(Math.abs(vectorA[i] - vectorB[i]));
			}
 
			trace(dist);
			return dist;
		}
	}
 
 
}

Картинки грузил в лоб, не пинайте)

Можно настраивать точность с помощью изменения переменных whiteThreshold, blackThreshold и epsilon
Как оказалось, без обрезки гистограммы можно вполне обойтись
Проверил на четырех фотках - определяет правильно все)

Если же все таки обрезать - то сумма значений whiteThreshold и blackThreshold не должна превышать 255, я не делал проверку. (у нас 255 уровней яркости)
=============================
Небольшая поправочка - попробовал поменять размер картинок с 500х500 до 150х150, оказывается не учел количество пикселей при сравнении картинок. Надо переделать функцию сравнения, чтобы считала проценты пикселей с заданной яркостью, а не само количество пикселей

Код AS3:

private function findDistinction(vectorA:Vector.<Number>, vectorB:Vector.<Number>):Number
		{
			var dist:Number = 0;
 
			var firstSum:Number = 0;
			var secondSum:Number = 0;
			for (var i:uint = 0; i < vectorA.length;i++ ) 
			{
				firstSum += vectorA[i];
			}
			for (i = 0; i < vectorB.length;i++) 
			{
				secondSum += vectorB[i];
			}
			trace(firstSum);
			trace(secondSum);
			for (i = 0; i < vectorA.length; i++)
			{
				dist += Math.sqrt(Math.abs(vectorA[i]/firstSum - vectorB[i]/secondSum));
			}
 
			trace(dist);
			return dist;
		}

И поменять значение переменной epsilon на 2 или 3.
Теперь можно сравнивать даже изображения с разным размером, у меня во всех случаях при epsilon = 2 правильно определило

Котяра · 01.03.2013, 22:50

О, класс, про therehold я и не подумал. Хотя особо не думал.
Вообще я про свою задачу для arp:
https://bitbucket.org/k0t0vich/arp

Цитата:

проверка на аналогичность тайлов со степенью похожести

Завтра буду думать.

Sync · 02.03.2013, 02:02

Почему нет предложений про нейросеть? Удобная же задача)))

wvxvw · 02.03.2013, 04:40

Сравнение такого плана (опознание картинок не точно похожих друг на друга) - это задача из области самообучающихся програм... Но, естесственно, если можно как-то схитрить, то имеет смысл (т.е. если картинки, за исключением группы пикселов идентичны, а не просто похожи.

Что да имело бы смысл сделать: изначально сравнивать не все картинки со всеми картинками, а вычислить хеш от каждой картинки, и сравнивать хеши (если создать хеши длиной 32 бита, то сравнения будут очень быстрыми). Можно воспользоваться CRC для этого, или тот же MD5 - главное быстрый алгоритм и короткий хеш.

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

Еще варианты: для предварительной фильтрации использовать вычисление гистограмы, или усредненного цвета всей картинки.

Добавлено через 2 минуты

Цитата:

Сообщение от Sync

Почему нет предложений про нейросеть? Удобная же задача)))

Нейронные сети сами по себе очень непростой вопрос. Если уж что-то самому организовывать, то support vector machine было бы проще реализовать... но простота тут относительная

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

Котяра · 02.03.2013, 12:46

Олег какой такой md5? Картинки не на 100% идентичны.

wvxvw · 02.03.2013, 13:39

Цитата:

Сообщение от Котяра

Олег какой такой md5? Картинки не на 100% идентичны.

Я же прямым текстом и написал:

Цитата:

Но, естесственно, если можно как-то схитрить, то имеет смысл (т.е. если картинки, за исключением группы пикселов идентичны, а не просто похожи.