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

[Scholium]

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

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

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

Есть ли у вас какие-либо идеи на эту тему? Можно без формул.

[Scholium]

Уточню формулировку задачи.

Бинарные матрицы символов это матрицы размерности n*m, где каждая ячейка может принимать значения только 0 или 1. При этом сумма всех единиц в матрице больше нуля.

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

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

Считается, что матрицы с одинаковым хэш-кодом похожи. Это отличный критерий для группировки, но он слишком точный. Нас больше устроит, когда количество различающихся битов в хэш-кодах двух матриц не превышает, скажем, 5% от 64 = 3 (округляем до целого). А группировать по этому критерию уже проблематично.

Как вариант, можно делать точное сравнение по хэш-коду, но понижать размерность сжатых матриц. Скажем, до 7*7, 6*6, 5*5, 4*4. Но тут можно с водой выплеснуть и ребенка. Пока я собираюсь экспериментировать со всеми этими вариантами и их комбинациями. Однако хотелось бы знать более надежные критерии.

[slavav]

Слово хэш в данном случае не годится. Хэш обозначает разрывное перемешивающее отображение, когда близкие значения после хеширования сильно различаются (поменяли один бит - совершенно другой хэш).
Вам, наоборот, нужно непрерывное отображение.
По делу: если матрицы одного размера то посчитайте количество различающихся пикселей (вы и сами это предлагали. Это почему-то не подходит?).
Если матрицы разного размера, то масшабируйте их в один размер. Полученные матрицы будут уже не бинарными, а вещественными, со значениями в единичном отрезке. Сосчитайте сумму квадратов разниц пикселей. Это даст вам расстояние.

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

-- 21.08.2020, 13:58 --

Вы будете двигаться быстрее если воспользуетесь опытом других: https://en.wikipedia.org/wiki/Optical_character_recognition.

[mihaild]

И тут еще будет проблема - просто выделение двух цифр и наложение друг на друга по верхнему левому углу будет работать плохо - сдвиг на один пиксель будет сразу приводить к большому отличию.

[Scholium]

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

Вы будете двигаться быстрее если воспользуетесь опытом других: https://en.wikipedia.org/wiki/Optical_character_recognition.

Я имею представление о существующих способах распознавания символов. Ключевые моменты там большие данные и машинное обучение. Поэтому ваша ссылка мне ничего нового не дает. В данном случае, нас интересует расстояние Хэмминга ( https://ru.wikipedia.org/wiki/Расстояние_Хэмминга ), для вычисления которого вычисляется значение, называемое хэшом (https://habr.com/ru/post/120562). Поэтому я тоже использую это название.

slavav писал(а):

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

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

Мне нужно не столько «непрерывное отображение», сколько критерий группировки для похожих символов. Однако критерий похожести имеет смысл только для пары матриц символов. Но это отношение не эквивалентно, т.е., если матрица А похожа на матрицу Б, а матрица Б похожа на матрицу С, то матрица А не обязательно должна быть похожа на матрицу С. Например, выберем критерий похожести, различие не более, чем в одной точке сравниваемых матриц. При этом возможна ситуация, когда пара матриц А и Б и пара Б и С различаются только в одной точке, а матрицы А и С уже в двух, что не соответствует выбранному критерию сравнения.

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

slavav писал(а):

По делу: если матрицы одного размера то посчитайте количество различающихся пикселей (вы и сами это предлагали. Это почему-то не подходит?).

Подходит, только это годится для поиска конкретной матрицы, как я уже упоминал, а не для их группировок.

slavav писал(а):

Если матрицы разного размера, то масшабируйте их в один размер. Полученные матрицы будут уже не бинарными, а вещественными, со значениями в единичном отрезке. Сосчитайте сумму квадратов разниц пикселей. Это даст вам расстояние.

Вы повторяете мои слова. Матрицы не будут вещественными, в этом нет никакой необходимости. Похоже, мы просто по-разному понимает одинаковые слова. Есть черный растровый символ, представленный на белом фоне в одной матрице и точно такой же, но другой размерности в другой матрице. Белая ячейка – ноль, черный пиксель – единица. Нет никаких вещественных матриц от слова «совсем». Сумма квадратов здесь это плохой критерий для сравнения похожих матриц, так как одной сфере с общим радиусу может принадлежать много различных матриц. Нас устраивает только попиксельное сравнение с небольшим отклонением, но это отношение не является эквивалентным.

slavav писал(а):

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

Мы приводим произвольные матрицы к одному размеру. В их ячейках только нули и единицы, что до, что после. Из 64 битов подобной матрицы мы получаем любым единообразным способом 64-битное число. Оно может служить критерием для сравнения и группировки похожих матриц только в случае равенства хэш-кода. Причем порядок хэша нас не интересует. А общие матрицы, с одинаковым хэшем можно усреднить. Нам нужно только сокращение мощности исходного множества. Например, был вначале миллион символов (матриц). Мы убрали абсолютно точные дубликаты, стало 30 тысяч символов. Мы применили группировку по равенству расстояния Хэмминга, стало 7 тысяч символов. Но это все равно много, поскольку в алфавите порядка 100 символов. Дл дальнейшего сокращения нужны дополнительные идеи.

[Sender]

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

просто выделение двух цифр и наложение друг на друга по верхнему левому углу будет работать плохо

Можно по центру масс совмещать.

[mihaild]

Sender в сообщении #1480155 писал(а):

Можно по центру масс совмещать

Да, это уже даст сильно лучший результат. Но всё равно возможны странные результаты (например небольшой поворот всё сломает; но в субтитрах наверное поворот редко встречается).

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

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

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

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

И если вы хотите сгруппировать символы - то для этого не обязательно нужно отношение эквивалентности. Берете какую-нибудь хорошую функцию расстояния и кластеризуете.

[Scholium]

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

И тут еще будет проблема - просто выделение двух цифр и наложение друг на друга по верхнему левому углу будет работать плохо - сдвиг на один пиксель будет сразу приводить к большому отличию.

Смотрите, как работает поиск по фотографии в Яндексе? Грубо, фото сжимается до размера 8*8, убирается цвет до оттенков серого, вычисляется бинарное значение, как признак выше среднего для серого или нет. Для матрицы получают 64-битное хэш-значение любым выбранным способом. Этот хэш сравнивается с хэшами в базе данных изображений, т.е., осуществляется поиск по индексу. Найденные, полноразмерные изображения могут быть похожими на микроскопический оригинал. Проделайте поиск по любому вашему фото в ya.ru, убедитесь сами. Иногда даже можно найти человека по его фотографии.

Указанные преобразования мало чувствительны к сдвигам, поворотам и другим преобразованиям оригинала. Детали можно найти в Интернете, либо в статье на Хабре, данной мной выше.

-- Пт авг 21, 2020 18:31:33 --

Sender в сообщении #1480155 писал(а):

Можно по центру масс совмещать.

Можно, но получается плохо для разноразмерных матриц. Нужно, по любому, выравнивать их по сторонам.

[Scholium]

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

Да, это уже даст сильно лучший результат. Но всё равно возможны странные результаты (например небольшой поворот всё сломает; но в субтитрах наверное поворот редко встречается).

Центрирование без масштабирования малополезно. Повороты – не актуальны, поскольку изначально текст в кадрах видео формировался программно.

mihaild писал(а):

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

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

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

Очень интересная информация! Может быть, даже пригодится, но надо разбираться. Спасибо!

mihaild писал(а):

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

В реале не все так просто, как кажется. «Современные методы» мне доступны, это опенсорсные OpenCV, SDL, FFPlay и другие. Там нужны большие данные и машинное обучение, что для моей задачи как бы лишнее. Конкретная задача позволяет использовать более простые методы и алгоритмы. Да и интересно самому разобраться в алгоритмах, а не тупо использовать чужое. Пока все получается. Даже в этой задаче можно нащупать кое-какие практические реализации, которые, я надеюсь, дадут приемлемый результат.

А на счет, что мне нужно, могу рассказать.

Есть такая французская певица Изабель Жеффруа (Isabelle Geffroy – ZAZ). Я просто в восторге от ее:
«Dans ma rue» : https://www.youtube.com/watch?v=MOk5yYLAQvU .
«Les Passants» : https://www.youtube.com/watch?v=tM5LlNeDtN0 .
«On ira» : https://www.youtube.com/watch?v=KPt5220n3Q0 .
«Que vendra» : https://www.youtube.com/watch?v=6THHrPyZQuQ и др.

Она разбудила во мне интерес к изучению французского языка. Что удивительно, на Ютубе есть прекрасные материалы для изучения иностранных языков. Например, сотни роликов «Easy French» (скажем, https://www.youtube.com/watch?v=bb4zvZdrMz4 ). Идеальные ролики для меня, но второй язык там английский. А я хочу русский.

Таким образом, я задумал написать обучающую программу, которая модернизирует существующие обучающие ролики до приемлемого состояния. В данном случае, убрать английский текст и написать вместо него русский. Французский текст распознать и перевести. При необходимости убрать из видео звуковые паузы и рекламу. Далее, интерактивное проигрывание видео. Это часть уже почти реализована на базе FFPlay. Хочу еще выбранный интервал проигрывать заданное количество раз и все такое, по мелочам.

Кроме «Easy French» можно использовать также ролики французского TV и вообще любое видео со встроенными субтитрами в фиксированном местоположении. Скажем учить язык по видео такой красавицы, как Marianne Beseme ( https://www.youtube.com/watch?v=32PAh5gNYqE )

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

mihaild писал(а):

И если вы хотите сгруппировать символы - то для этого не обязательно нужно отношение эквивалентности. Берете какую-нибудь хорошую функцию расстояния и кластеризуете.

«Хорошая функция расстояния» это расстояние Хэмминга. Другое дело, что с его помощью группировку символов на классы эквивалентности не сделаешь, поскольку оно не обладает отношением эквивалентности. Значит нужно выкручиваться как-то по-другому, типа использовать нулевое расстояние Хэмминга между сравниваемыми матрицами, но для матриц меньшей размерности, не 8*8, а 7*7 и ниже.

[mihaild]

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

Смотрите, как работает поиск по фотографии в Яндексе?

Я сильно сомневаюсь в том, что поиск по изображениям всё еще работает на тех же методах, что и 10 лет назад.

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

Указанные преобразования мало чувствительны к сдвигам, поворотам и другим преобразованиям оригинала

Это не так. Даже сдвиг на 1 пиксель переводит часть исходных пикселей в другую область сжатой картинки. И там легко может получиться что-то странное.

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

Там нужны большие данные и машинное обучение, что для моей задачи как бы лишнее

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

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

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

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

[Scholium]

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

Я сильно сомневаюсь в том, что поиск по изображениям всё еще работает на тех же методах, что и 10 лет назад.

Это не так. Даже сдвиг на 1 пиксель переводит часть исходных пикселей в другую область сжатой картинки. И там легко может получиться что-то странное.

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

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

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

mihaild писал(а):

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

Мое «машинное обучение» это ручное распознавание относительно небольшого количества символов, нужно порядка нескольких сотен для первого видео. Пока я имею несколько тысяч, что много.
Артефакты и эвристика не вопрос. Все уже убрано и подготовлено. Качество символов хорошее, различие для похожих символов в несколько процентов вполне допустимо.

Чужие модели мне неинтересны, да использовать их не так-то просто. Думаю, что рано или поздно я найду удовлетворяющий меня эмпирический критерий.

mihaild писал(а):

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

Согласен, можно, но не для расстояния Хэмминга. Я уже упоминал о сортировке по параметрам символов и их построчному разложению. Для первого приближения неплохо. Но пока не идеально. Думаю еще поиграться с параметрами. Например, вместо собственной высоты и ширины символа использовать их отношение (похожие символы должны иметь похожие пропорции, чем не инвариант?). Возможно, в критерии общую высоту текстовой строки надо убрать, но оставить отступ сверху и номер строки (поскольку, в «Easy French» первая строка французская, а вторая – английская). Вместо построчного содержимого оригинальной матрицы использовать построчное содержимое ее сжатого эквивалента и т.д. и т.п. Что-нибудь должно сработать.

[kotenok gav]

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

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

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

[mihaild]

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

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

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

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

нужно порядка нескольких сотен для первого видео.

При таких объемах простая линейная модель уже имеет шансы обучиться.

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

можно, но не для расстояния Хэмминга

А чем оно тут хуже любого другого?

[Scholium]

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

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

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

mihaild писал(а):

При таких объемах простая линейная модель уже имеет шансы обучиться.

Это все абстрактно, а мне нужно конкретно!

mihaild писал(а):

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

можно, но не для расстояния Хэмминга

А чем оно тут хуже любого другого?

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

[mihaild]

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

А сжатые останутся похожими, но станут одинаковой размерности

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

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

а мне нужно конкретно

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

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

сортировка по последовательности параметров матриц и ее содержимому

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