Как группировать бинарные матрицы по степени их похожести?

[Scholium]

mihaild в сообщении #1480216 писал(а):

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

А что представлять, у меня большинство символов такие. Но вы думаете, что в сжатых матрицах этот эффект сохраниться? В значительных случаях нет, поскольку сжатие обнуляет подобные тонкости.

Более того, я даже вынашивал идею сравнения оригинальных матриц без их сжатия, но близкой размерности. Например, один символ 45*35 пикселей, а второй 43*37. Просто делаем все возможные сравнения со всеми допустимыми смещениями одной матрицы относительно другой. А выбираем то смещение, которое дает минимум расстояния Хэмминга. Так что «один пиксель мусора» нам погоды не сделает (и даже два!). Но проблема, как уже много раз указывалось, в том, что этот критерий не годится для группировки, только для поиска заданной матрицы в базе данных.

mihaild писал(а):

Конкретно: идете в википедию и читаете про линейные модели. Потом идете в гугл и находите, что есть для их обучения для используемого вами языка.

Конкретно нужна мотивация, а для мотивации достаточно намека. А так Википедия большая, читать есть много чего. Вот вашу информацию про locality-sensitive hasing я держу в уме, на свежую голову обязательно посмотрю внимательней. А пока идей для экспериментов мне хватает.

mihaild писал(а):

Тут вы хотите вложить матрицы в одномерное пространство. В таком виде нельзя задать, что, например, 0, 6 и 9 все больше похожи на 8, чем друг на друга.

Совершенно не факт! В сортировке участвует построчное разложение символов, а оно будет заметно отличаться для названных вам цифр. Более того, при подобной сортировке я делаю попарные сравнения, т.е., вычисляю искомое расстояние Хэмминга. Пока оно мало, последовательность матриц идет в одну группу, как только резко увеличилось, мы закрываем старую группу, и открывает новую, для которой продолжаем попарное попиксельное сравнение.

mihaild писал(а):

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

Опять, недостаточно намека, но термин, я на всякий случай запомнил.

mihaild писал(а):

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

Опять же, это все абстрактно. Вот если я смог прикрутить FFplay к своему проекту, то получил собственный видеопроигрыватель. А там мне просто непонятно, что куда прикручивать. Но от своих велосипедов я вполне могу выйти на профессиональные алгоритмы OpenCV. Но эту библиотеку нужно изучать серьезно, как матанализ Камынина, к примеру.

-- Пт авг 21, 2020 22:23:32 --

kotenok gav в сообщении #1480208 писал(а):

Scholium в сообщении #1480192 писал(а):

В данном случае, убрать английский текст и написать вместо него русский.

Скажем, Яндекс.Переводчик умеет переводить с картинки.

Смотрите, у меня видео, а не картинка. Пока персонаж скажет одну фразу, пройдет несколько секунд. При 25 кадрах в секунду это порядка сотни изображений с одним и тем же текстом. Мне что переводить все из них? Смысл, вытащить уникальную текстовку, в данном случае французскую, а перевести можно любым переводчиком. Я пользуюсь Гугловским, переводит очень хорошо. А английский текст надо затереть, но так, чтобы видео фон не искажался. А на его место написать русский текст. Потом мы это видео проигрываем в нашем собственном видеопроигрывателе (который уже реализован на базе FFplay). Дополнительно добавляем интерактивные возможности, например, видео прокрутку одной фразы несколько раз. А для этого надо добавить возможность разметки видео и прочие специфические настройки, типа указать размеры текстовой области на видео (с помощью мыши). Так что простой перевод картинки нам не нужен.

[Scholium]

mihaild писал(а):

slavav в сообщении #1480128 писал(а):

Хэш обозначает разрывное перемешивающее отображение

Есть locality-sensitive hasing, который как раз про "непрерывные" хэши. В общем случае, хэш - это просто отображение из пространства большой размерности в пространство меньшей.

Посмотрел я вашу ссылочку и субссылочки в ней, и понял, что это не совсем то, что мне нужно. Вы правильно взяли в кавычки слово «непрерывные». Естественно, что они не могут быть непрерывными, только псевдо непрерывными. Эти хэши близки в смысле расстояния Хэмминга, что как мы уже выяснили, нас мало устраивает.

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

Алгоритм группировки бинарных матрицы разной размерности по степени их похожести

– Избавляемся от точных дубликатов, путем помещения в упорядоченное множество std::set построчной развертки оригинальной матрицы.

Параметры матриц символов

1. Номер текстовой строки (если это принципиально).

2. Порог отступа сверху (относительно текстовой линии) для данного символа. Порог может принимать три значения: верхний символ (большие буквы, апостроф, «шляпка» и т.п.), средний символ (малые буквы, плюс, минус и т.п.), нижний символ (точка, запятая, нижнее подчеркивание и т.п.).

3. Процент собственной ширины от собственной высоты данного символа.

4. Хэш-код сжатой, до размера высоты, равной 8 пикселям, матрицы. Если текущая высота символа равна 8 пикселям, то преобразование не делаем (оно тождественно оригиналу), а если меньше, то увеличиваем до 8 пикселей.

5. Содержимое (построчная развертка) оригинальной матрицы (ранее полученное).

– Строим линейный код матрицы по ее параметрам.

– Помещаем этот код в упорядоченное множество std::set либо в отображение std::map, с ключом 1 - 4 и значением в виде вектора std::vector строк 5.

– Делаем группировку матриц для одинаковых параметров 1 – 4 (для отображения std::map ничего делать уже не надо).

База минимальной побитовой разницы попарного сравнения (т.е., расстояния Хэмминга для хэш-кода, не превышающего разницы, например, в 3 бита) здесь не годится. Но работает расстояние Хэмминга для хэш-кода равного нулю (как описано в алгоритме).

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

[mihaild]

Scholium в сообщении #1480314 писал(а):

что как мы уже выяснили, нас мало устраивает

Ну это вас оно мало устраивает. Я всё еще не понимаю, чем плохо взять расстояние и покластеризовать по нему.

[Scholium]

mihaild в сообщении #1480339 писал(а):

Scholium в сообщении #1480314 писал(а):

что как мы уже выяснили, нас мало устраивает

Ну это вас оно мало устраивает. Я всё еще не понимаю, чем плохо взять расстояние и покластеризовать по нему.

Кластеры это те же классы эквивалентности. А расстояние Хэмминга, большее нуля, не обладает отношением эквивалентности, только равное нулю. Нулевое расстояние Хэмминга означает группировку по хэшу, т.е., одному хэш-значению соответствует группа похожих матриц.

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

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

В нашем алгоритме за построение кластеров отвечают признаки 1 - 3. Их можно убрать совсем, тогда хэш-значение 4 может стать плохим критерием группировки, при любой своей размерности. А можно, наоборот, увеличить количество признаков для естественной кластеризации. При этом признак 3 можно брать не с точностью до процента, а с точностью до нескольких процентов.

В качестве дополнительных признаков можно пробовать использовать относительную площадь символа, относительные координаты его центра масс, а также критерии тестирования. Под тестированием можно, например, понимать определение наличия «точки» символа (скажем, размером 2*2 или 4*4 пикселя) в заданном месте, допустим, в центре символа, в его углах и посередине крайних сторон и т.д. В зависимости от того черные это пиксели или белые, мы получаем дополнительный критерий естественной кластеризации.

Кстати, поначалу я именно метод тестирования использовал для распознавания символов. Работало неплохо, но была привязка к одному типоразмеру шрифта. При использовании относительных параметров этот критерий вполне можно развивать.

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

-- Вс авг 23, 2020 15:00:21 --

P.S. При вычислении собственной высоты или ширины символа можно обращать внимание на количество пикселей цвета символа в крайних линиях матрицы. Если там в одной строке или ряду находится только один такой пиксель, то, с большой вероятностью, это ложный пиксель (образованный за счет флуктуации при бинаризации исходного изображения). Очевидно, его вполне можно убрать. Более того, даже два или три не подряд идущие подобные пиксели также могут быть случайными. Тем самым мы можем более точно вычислять собственные размеры символа и их отношение.

[mihaild]

Scholium в сообщении #1480375 писал(а):

Кластеры это те же классы эквивалентности. А расстояние Хэмминга, большее нуля, не обладает отношением эквивалентности, только равное нулю

Да, но при кластеризации наше отношение эквивалентности не обязано быть функцией от расстояния.
Например если мы кластеризуем точки $\{1, 2, 3, 4\}$$ в кластера $\{1, 2\}$ и $\{3, 4\}$, то это вполне 2$ и $3$ из разных кластеров такое же, как между точками $1$ и $2$ из одного кластера.

Scholium в сообщении #1480375 писал(а):

Но, поскольку, с расстоянием Хэмминга непересекающихся множеств или кластеров не получишь

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

[Scholium]

mihaild в сообщении #1480378 писал(а):

Да, но при кластеризации наше отношение эквивалентности не обязано быть функцией от расстояния.

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

mihaild писал(а):

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

И чем это отличается от хеширования? Для построения практического алгоритма я исхожу из своего определения, что кластеризация это естественная группировка, а хеширование – искусственная.

-- Вс авг 23, 2020 15:34:49 --

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

[Scholium]

Ради интереса хочу рассказать о нюансах реализации указанного алгоритма.

Прежде всего, возникли идеи оптимизации процесса. А именно:

1. Зачем обрабатывать все кадры с одинаковым текстом, если можно обработать только один кадр?

2. Зачем делать посимвольное распознавание, если можно делать распознавание вручную всего ключевого кадра сразу? Для одного ролика «Easy French» таких кадров порядка сотни, состоящих из двух строк текста.

3. Почему бы при ручном распознавании не привязаться к номеру символа, в текущей строке, группы однотипных кадров? Тогда, на этапе экспериментально-аналитическом мы будем иметь заранее распознанный текст, который уже можно анализировать по любым признакам.

4. Различать бинаризированные текстовые области кадров видео можно по некоторому хэш-коду.

Этот подход сильно упрощает процесс программирования.

Для различия текста в ключевых кадрах, я сначала использовал хэш размерности 8*8, потом 8*16, но при этом «терялись» некоторые значимые фреймы. В итоге, подходящим оказался хэш, размерности 10*20 битов. Однако при этом стали появляться избыточные дубликаты, в соотношении три к одному. Вот этот момент для меня оказался новым.

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

Правда, остается еще один момент для физически сцепленных символов, которые нельзя разделить некоторой кривой без пересечений. Это могут быть символы типа «ff», «tt», «ft» и др. В силу этого, потребуется дополнительно выводить текст ключевого кадра посимвольно, что несколько усложняет интерфейс программы.