Восстановить бинарную матрицу по суммам строк и столбцов

Здравствуйте

Имеется такая задача. Дана бинарная матрица размером MxN, т.е. ее элементами могут быть или нули, или единицы. Для матрицы известна сумма элементов по столбцам, и по сторам. По сути, это значит, что в сумма элементов в строке равна числу единиу в строке. Задача: восстановть матрицу, т.е. расставить единицы по матрице, чтобы суммы были верны. Любую сумму в строке или столбце можно разбить не более чем на 2 элемента: т.е. если сумма элементов строки равна 3, то это будут пары 2+1, или 1+2, если 4 - то 1+3, 2+2, 3+1, и т.д. для остальных элементов. Последовательность элементов больше 1 всегда идут друг за другом (если 2, значит в двух ячейках подряд цифра 1).

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

В какую сторону копать?

Спасибо

0

Во вложении 2 файла для шестиугольного сплошного алюминиевого профиля. Тот, который с нечеткими границами и россыпью пикселей - иттерационный метод. Тот который почетче - после некоторых ухищрений. Это по 2 проекциям. По 5 или 8 - вообще сказка была бы, но 5 и 8 проекций стоит намного дороже.

0

Это вы купили установку а алгоритма обработки кадра или софта не было? Или софт просто дорого и не купили? =)

Сообщение от eskofen Это по 2 проекциям.

А зачем нужен рентген рисующий абстрактную кашу из пикселей вместо изображения? Какую инфу он вообще несет? Или это дальше очень сложная обработка и из каши пикселей получают полезную инфу о форме?

Сообщение от eskofen По 5 или 8 - вообще сказка была бы

А нельзя поворачивать рентген в N положений?
https://ru.wikipedia.org/wiki/Мальтийский_механизм
Это у вас рентген в параллельных лучах?
А если запускать каждый излучатель по очереди а преемники использовать все что есть, будет веерный рентген от одной точки. Получается много ракурсов и по идее сильно вырастает разрешение.
Может сработают не все приемники а пару соседних. Совершенно другой алгоритм обработки.

0

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

0

eskofen, если картинка 200x200 и решение только одно, то достаточно обратить разреженную симметричную матрицу из единиц и нулей размером 40000x40000...

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

Добавлено через 10 минут
А вообще, Excalibur921, прав. Это преобразование Радона. На эту тему есть масса специальной литературы по восстановлению изображения из проекций.

0

Сообщение от Excalibur921 Это вы купили установку а алгоритма обработки кадра или софта не было? Или софт просто дорого и не купили? =)

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

Сообщение от Excalibur921 А зачем нужен рентген рисующий абстрактную кашу из пикселей вместо изображения? Какую инфу он вообще несет? Или это дальше очень сложная обработка и из каши пикселей получают полезную инфу о форме?

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

Сообщение от Excalibur921 Если наклонить рентген под углом к трубе то можно использовать все датчики по одной оси. Изменяя угол наклона можно задействовать всегда все датчики в зависимости от диаметра трубы.

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

Сообщение от u235 Это преобразование Радона.

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

Сообщение от u235 На эту тему есть масса специальной литературы по восстановлению изображения из проекций.

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

0

Сообщение от eskofen получить профиль трубы

Каша пикселей это далеко не профиль…

Сообщение от eskofen имеем некую априорную информацию (труба)

Может обработка проекций вообще не нужна?
По идее выход тут только брать эталонную трубу и не похожесть каши пикселей или даже просто проекций от эталона и брака есть критерий оценки… Единственно нужно наверно одинаковая ориентация эталона и исследуемого тела.

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

Сообщение от Excalibur921 обработка проекций вообще не нужна?

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

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

Добавлено через 1 час 38 минут

Сообщение от Excalibur921 минимум трех неизвестных

Если форма кривой проекции слабо чувствительна к сдвигу трубы( очень узкие диаграммы направленности излучения) по XY то будет 1 неизвестная вместо 3, просто угол поворота модели трубы.

Тогда так:
Задана математическая модель трубы.
Получаем проекции реальной трубы.
Ищем угол поворота модели(минимум 1 неизвестной) сверяя искусственные проекции от модели и настоящие от рентгена.
Если проекции похоже то брака нет. Зная в каком месте проекции графики не похоже там и брак.

0