🎄 😼 🥗 Transformación rápida de Hough: de Elbrus a COMDIV 🤲🏽 👊 📖

Durante cinco años, en Smart Engines les hemos estado contando cómo optimizamos nuestro software para la arquitectura del procesador Elbrus. Por lo general, compartimos con usted resultados encantadores, cuando en Elbrus logramos reconocer casi tan rápido como en los mejores procesadores extranjeros. El artículo de hoy está dedicado a la descripción de los "componentes internos" optimizados de un algoritmo que es extremadamente importante para todos los sistemas de visión por computadora: la transformación rápida de Hough. Además, le informaremos sobre otra familia de arquitecturas domésticas extremadamente interesante: los microprocesadores KOMDIV.

¿Qué es la transformada de Hough y cuándo se usa?

1959 1. , ,, , , . ,... , – , . , 2, 3.

- , . .

. . 4. – 2. . , , 5 6 , 7.

Visualización de la aplicación de la transformada de Hough para corregir aberraciones ópticas

: O (N ^ 3) , norte – . ? «» norte . – N ^ 2 , norte . , – .

, - . 1998 .. 8. « » , , . $O (N ^ 2 \ log {N})$ .

" ". , «» «» . , . «» «» . . $N \ veces N$ , $O (\ log {N})$ .

(s, 0) (s + t, N) , – , – , norte – . (S t) -, .

. $N \ veces N$ $N = 2 ^ k, k \ in \ mathbb {N}$ . MATLAB, 9.

function h = fht2(I)
n = size(I, 2);
if n < 2
h = m;
return
end
h = mergeHT(fht2(I(:, 1 : n / 2, :)), fht2(I(:, (n / 2 + 1) : n, :)));
end

function h = mergeHT(h0, h1)
[m, n0, o] = size(h0);
n = 2 * n0;
h = zeros(m, n, o);
r = (n0 - 1) / (n - 1);
for i = 1 : n
t = i - 1;
t0 = round(t * r);
s = t - t1;
h(:, i, :) = h0(:, t0 + 1, :) + [h1(s + 1 : m, t0 + 1, :); h1(1 : s, t0 + 1, :)];
end
end

, . , norte , N = 2 ^ k – . , , -. , , « », , , .

, , «» , MATLAB:

;
.

«» . . , , .

«» – . , fht2core

. , mergeHT

, , . , [0; N-1] -. , , 2N-1 . – , mergeHT

.

FHT

, . « », . .

, , . , EML, .

, , .

, , :

. ?

. -64. ?

-64 – 64- , - . MIPS IV ISA.

18909 65 , 1 80 .

SoC 18909 CPCA. CPCA 64 , , – 4 SIMD. 64 64 64- . 16 16 . / , – 16 / . CPCA MIPS64 Release 1. , 18907. 16 /. .

CPCA – 32- ISO 60559. 10 , « », . « 2x2- 2d-» « », , 8 . , CPCA 800 32 10 ./ 4 800 25.6 .

, , . CPCA 4.2 . , 2 4 – psadd, .. 6.4 800 , 4 2 , .. 19.2 / 800 . 4 / 12.8 / 800 . , 1.5 .

, DDR3 18909 400 , CPCA 6.4 / 16 / 400 1.6 /. 533 3 a/. 1.6 /. , , .

, CPCA 12% 2% . CPCA. , , CPCA . , :

4 , 1 2 ;
12% ;
CPCA, – .

mergeHT

h0

h1

n n , , . , n0 = n1 = n / 2

, . , , , , .

/ CPCA 1.5 : . 800 , CPCA 18%.

, . CPCA. , 1.88 / 32 . , , , 470 .

5439 × 5439 1.1 / 406 , 86% . . , 512 × 512 116 (49 ./), 1024 × 1024 –191 (18 ./), 2048 × 2048 – 286 (6 ./), 4096 × 4096 – 378 (1.8 ./).

. -, , ( ). -, , , , . , .

«» .

« CPCA», . . , . . , . . , . . , . . , «».

Hough P. Machine analysis of bubble chamber pictures // Proc. of the International Conference on High Energy Accelerators and Instrumentation, Sept. 1959. – 1959. – P. 554-556.
Mukhopadhyay P., Chaudhuri B. B. A survey of Hough Transform // Pattern Recognition. – 2015. – Vol. 48. – No. 3. – P. 993-1010.
Hassanein A. S. et al. A survey on Hough transform, theory, techniques and applications // arXiv preprint arXiv:1502.02160. – 2015.
Duda R. O., Hart P. E. Use of the Hough transformation to detect lines and curves in pictures // Communications of the ACM. – 1972. – Vol. 15. – No. 1. – P. 11-15.
. ., . ., . . // . – 2017. – . 31. – №. 4. – . 331-342.
Nikolaev D. P., Nikolayev P. P. Linear color segmentation and its implementation // Computer Vision and Image Understanding. – 2004. – Vol. 94. – No. 1-3. – P. 115-139.
Kunina I. A., Gladilin S. A., Nikolaev D. P. Blind compensation of radial distortion in a single image using fast Hough transform // Computer Optics. – 2016. – Vol. 40. – No. 3. – P. 395-403.
Brady M. L. A fast discrete approximation algorithm for the Radon transform // SIAM Journal on Computing. – 1998. – Vol. 27. – No. 1. – P. 107-119.
. ., . ., . . // . – 2017. – . 17. – №. 4. – . 294-308.

Transformación rápida de Hough: de Elbrus a COMDIV

¿Qué es la transformada de Hough y cuándo se usa?

FHT

. ?

More articles: