Recuperando a inclinação de uma linha digitalizada

Houve algum trabalho para recuperar a inclinação de um segmento de linha de sua digitalização? Não se pode fazer isso com perfeita precisão, é claro; o que se quer é um método de derivar de uma linha digitalizada um intervalo de possíveis inclinações.

(A noção de uma linha digitalizada que estou usando é Rosenfeld de: o conjunto de pares , onde i varia ao longo dos números inteiros (ou um bloco de números inteiros consecutivos) e n i n t ( x ) indica o número inteiro mais próximo de x (se x = k + 1 / 2 , tomamos n i n t ( x ) = K ).)$(i,nint(ai+b))$$i$$nint(x)$$x$$x=k+1/2$$nint(x)=k$

Eu fiz alguns trabalhos por conta própria (consulte http://jamespropp.org/SeeSlope.nb ), mas não tenho formação formal em geometria computacional, portanto, suspeito que possa estar reinventando a roda, pois a pergunta parece ser essa. um básico.

De fato, eu sei que o método de regressão linear para estimar a inclinação está na literatura, mas não consegui encontrar meu resultado de nenhum lugar. (Este resultado diz que, se se escolhe um e b uniformemente aleatoriamente em [ 0 , 1 ] , então a diferença entre a inclinação de um da linha y = a x + b e a inclinação ¯ uma da linha de regressão aproximação dos n pontos ( i , $O(1/n^{1.5})$$a$$b$$[0,1]$$a$$y=ax+b$$\overline{a}$$n$ ( 1 ≤ i ≤ n ) tem desvio padrão O ( 1 / n 1,5 ) .)$(i,nint(ai+b))$$1 \leq i \leq n$$O(1/n^{1.5})$

Qualquer sugestão ou indicação de literatura relevante será muito apreciada.

Jim Propp ([email protected])

Veja Geração aleatória de palavras sturmianas finitas de Berstel e Pocchiola para obter uma prova de que a região viável do seu LP tem apenas três ou quatro lados, além de um algoritmo simples para encontrar o polígono dado o declive e a interceptação. (Eles estão lidando com o reconhecimento de palavras sturmianas, mas os problemas estão fortemente relacionados.)

Eles também fornecem uma enumeração explícita dos polígonos; portanto, é possível enumerar as áreas dos polígonos e as faixas das pistas, para que você possa obter o valor esperado da faixa de pistas (além de momentos mais altos). ) como uma soma explícita.

A abordagem da geometria computacional substituiria cada pixel (i, j) pelo segmento vertical (i, j + [- 1 / 2,1 / 2]), pegaria os cascos convexos dos conjuntos de pontos de extremidade superior e inferior e calcularia o comum interno tangentes - delimitam a faixa de declives que produzem essa linha digital. Essa é apenas a interpretação geométrica do programa linear que você menciona nos slides. O (n) tempo é suficiente para o LP de Meggiddo, ou para os cascos e tangentes de Graham-Yao.

E o método de transformação padrão de Hough usado para detecção de linha no processamento de imagens: http://en.wikipedia.org/wiki/Hough_transform ?

Se você quiser ganhar velocidade, pode usar a versão aleatória do HT.

• Não conheço nenhum trabalho em cg (ou qualquer outro grupo) sobre derivar a inclinação do conjunto de pontos discretos, mas isso é mais um reflexo da minha falta de conhecimento.

• $\Delta y$$\Delta x$$x$$y$$x$$y$