Найдите углы деформированного прямоугольника

Question

Я пытаюсь создать программу, которая автоматически исправляет перспективу прямоугольника. Мне удалось получить силуэт прямоугольника, и у меня есть код для исправления перспективы, но я не могу найти углы. Самая большая проблема в том, что, поскольку она деформирована, я не могу использовать следующий «код»:

  c1 = min(x), min(y)
  c2 = max(x), min(y)
  c3 = min(x), max(y)
  c4 = max(x), max(y)

Это не сработает в этой ситуации (X обозначает угол):

X0000000000X
.00000000000
..X000000000
.....0000000
........0000
...........X

Кто-нибудь знает, как это сделать?

Answer 1

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

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

Answer 2

Вы можете попытаться использовать алгоритм линии сканирования - для каждой линии многоугольника (так что y = min (y) .. max (y)), получите l = min (x) и r = max (x). Вычислите левый / правый уклон (дельтакс) и сравните его с уклоном предыдущей линии. Если это изменилось (используйте некоторый допуск здесь), вы находитесь в углу прямоугольника (или близко к нему). Это не будет работать во всех случаях, поскольку наклон не может быть таким точным из-за низкого разрешения, но для больших прямоугольников и наклонов, которые не слишком похожи, это должно работать.

По крайней мере, это хорошо работает для вашего примера:

X0000000000X l =  0, r = 11
.00000000000 l =  1, r = 11, deltaxl = 1, deltaxr = 0
..X000000000 l =  2, r = 11, deltaxl = 1, deltaxr = 0
.....0000000 l =  5, r = 11, deltaxl = 3, deltaxr = 0
........0000 l =  8, r = 11, deltaxl = 3, deltaxr = 0
...........X l = 11, r = 11, deltaxl = 3, deltaxr = 0

Вы начинаете с вершины прямоугольника, где вы получаете два разных значения для l и r, поэтому у вас уже есть два угла. С левой стороны, для первых трех строк вы получите deltax = 1, но после него вы получите deltax = 3, поэтому есть угол в (3, 3). С правой стороны ничего не меняется, deltax = 0, поэтому вы получаете только точку в конце.

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

В некоторых случаях простой deltax = (x - lastx) не будет работать хорошо, см. Этот пример для левой части прямоугольника:

xxxxxx
 xxxxx deltax = 1 dy/dx = 1/1 = 1
 xxxxx deltax = 0 dy/dx = 2/1 = 2
  xxxx deltax = 1 dy/dx = 3/2 = 1.5
  xxxx deltax = 0 dy/dx = 4/2 = 2
   xxx deltax = 1 dy/dx = 5/3 = 1.66

Иногда deltax равен 0, иногда равен 1. Лучше использовать наклон линии от фактической точки до верхней левой / правой точки (deltay / deltax). Используя его, вам все равно придется придерживаться допуска, но ваши значения будут уточняться с каждой новой строкой.

Answer 3

Вы можете использовать грубое преобразование, чтобы найти 4 наиболее заметные линии в маскированном изображении. Эти линии будут сторонами четырехугольника. Линии будут пересекаться до 6 точек, которые представляют собой 4 угла и 2 точки схождения перспективы.

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

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

en.wikipedia.org / вики / Hough_transform

Пример кода CImg

Мне было бы очень интересно узнать ваши результаты. Я думал о том, чтобы написать что-то вроде этого, чтобы исправить фотографии листов бумаги, сделанные под углом. В настоящее время я изо всех сил пытаюсь найти способ исправить перспективу, если известны 4 точки

приписка

Также проверьте Чжэнъю Чжан, Ли-Вэй Хэ, "Сканирование белой доски и улучшение изображения" http://research.microsoft.com/en-us/um/people/zhang/papers/tr03-39.pdf для более совершенного решения для обнаружения четырехугольников

Я задал связанный вопрос, который пытается решить перспективное преобразование: пропорции перспективно деформированного прямоугольника

Answer 4

Это похоже на проблему выпуклой оболочки.

http://en.wikipedia.org/wiki/Convex_hull

Ваша проблема проще, но должно работать то же самое решение.