패턴 인식에 대한 몇 마디. 2차원 데이터 배열로서의 비트맵 이미지 고전적 필터링: Fourier, LPF, HPF
문제의 공식화구현의 목적과 가능성에 따라 결정됩니다.
표적.직사각형 부품을 품질과 불량품으로 분류하는 프로그램을 개발하십시오.
작업 구현 기회컴퓨터의 능력에 의해 결정됩니다. 컴퓨터는 알고리즘 순서로 숫자 정보를 처리할 수 있습니다. 컴퓨터의 기능을 실현하려면 해결 중인 문제를 시뮬레이션해야 합니다.
컴퓨터를 사용한 모델링은 실제 개체(세계)에서 데이터 및 작업을 사용하여 속성에 대한 코드화된 설명으로의 전환을 의미합니다. 일반적으로 이러한 전환은 여러 단계로 수행됩니다.
추출- 작업 측면에서 개체의 가장 중요한 기능을 선택합니다.
작업의 목표에 따라 불필요한 모든 것을 버리고 모델링 대상에서 모델링 대상으로 이동할 수있는 연구가 필요합니다.
직사각형은 다른 사변형과 어떻게 다른가요?
- 반대쪽의 평등.
- 반대편의 평행성.
- 대각선의 평등.
- 모든 각도가 맞습니다.
문제를 고유하게 해결하는 데 필요한 최소 기능 수는 얼마입니까?
- 2개의 대변의 동일성 + 대각선의 동일성.
- 마주보는 두 변의 평행도 + 대각선의 동일성.
- 세 귀퉁이가 맞습니다.
그래서 추상화 덕분에 우리는 구두 정보 모델을 얻었습니다. 그러나 여전히 컴퓨터로는 이해할 수 없습니다. 알고리즘으로 제시되고 소프트웨어로 구현된 수학적 모델을 이해합니다.
작업 구현 방법론.
품질 부품(직사각형) 또는 결함 부품(사각형)의 도면은 AutoCAD 그래픽 시스템의 세그먼트(LINE 명령)에서 만들어 으로 내보냅니다. kntrs.lsp() 프로그램은 DXF 파일에서 선분 데이터(꼭지점 좌표)를 읽어 텍스트 파일 vrtks.txt에 라운드 로빈 순서로 기록합니다.
텍스트 파일 vrtks.txt는 도면에서 직접 정점의 좌표를 가져와 수동으로 생성할 수 있습니다.
개발된 rct.lsp 프로그램은 vrtks.txt 파일에서 데이터를 읽어 분석하고 result.txt 파일에 부품의 요구 사항 준수에 대한 기록(직사각형 여부)을 출력해야 합니다.
기능의 공식화
세그먼트 길이의 동일성(변 또는 대각선): 각 세그먼트의 길이는 세그먼트 좌표의 차이를 통해 직사각형 직사각형(피타고라스 정리에 따름)의 빗변으로 결정됩니다.
(setq DX12 (abs (- X1 X2))) (setq DY12 (abs (- Y1 Y2))) (setq DA1 (sqrt (+ (* DX12 DX12) (* DY12 DY12))))
라인의 평행성: K2=K1, 어디 에게직선의 기울기 케이=(Y2-Y1)/(X2-X1)
"직각"의 개념을 공식화하는 방법은 무엇입니까? 작업 세트의 프레임워크 내에서 "직각"의 존재 여부는 세그먼트의 직각도 기호로 확인할 수 있습니다. K2= -1/K1, 어디 에게직선의 기울기입니다. K=(Y-Y0)/(X-X0).
컴퓨터에 모델 표시
모든 정보는 결국 내부 기계 모델에 이진수(코드)를 사용하여 컴퓨터에 표시됩니다. 이전에는 프로그래머가 코딩을 했습니다. 이제 대부분의 프로그램은 알고리즘 언어로 만들어집니다.
오랫동안 나는 기본 방법에 대한 일종의 가이드 인 이미지 인식의 기본 사항을 포함하는 일반적인 기사를 작성하고 싶었습니다. 기본 방법을 사용할 때, 어떤 작업을 해결하는지, 저녁에 무릎을 꿇고 무엇을 할 수 있는지, 20대에 팀이 없으면 생각하지 않는 것이 좋습니다.
오랫동안 광학 인식에 관한 기사를 써왔기 때문에 한 달에 두 번 다양한 사람들이 이 주제에 대한 질문을 저에게 씁니다. 때때로 당신은 그들과 다른 세계에서 살고 있다는 느낌을 받습니다. 한편으로는 사람이 관련 주제의 전문가일 가능성이 높지만 광학 인식 방법에 대해서는 거의 알지 못한다는 것을 이해합니다. 그리고 가장 짜증나는 것은 그가 가까운 지식 분야의 방법을 적용하려고 시도한다는 것입니다. 논리적이지만 이미지 인식에서 완전히 작동하지 않지만 이것을 이해하지 못하고 그가 그에게 무언가를 말하기 시작하면 매우 불쾌합니다. 아주 기본. 그리고 기본부터 이야기하는 것은 많은 시간이 소요되는 경우가 많다는 점을 고려하면 더욱 안타깝습니다.
이 기사는 이미지 인식 방법을 한 번도 다루지 않은 사람이 10-15 분 이내에 주제에 해당하는 세계의 기본 그림을 머릿속에 만들고 어느 방향으로 파헤쳐 야하는지 이해할 수 있도록 설계되었습니다. 여기에 설명된 많은 방법은 레이더 및 오디오 처리에 적용할 수 있습니다.
잠재 고객 또는 광학 인식을 시작하려는 사람에게 항상 말하기 시작하는 몇 가지 원칙부터 시작하겠습니다.
- 문제를 풀 때는 항상 가장 단순한 것부터 시작하십시오. 사람을 따라가는 것보다 사람에게 주황색 레이블을 걸어 폭포에서 그를 강조 표시하는 것이 훨씬 쉽습니다. 초고해상도 알고리즘을 개발하는 것보다 고해상도로 카메라를 찍는 것이 훨씬 쉽다.
- 광학 인식 방법의 엄격한 문제 진술은 시스템 프로그래밍 문제보다 훨씬 더 중요합니다. TK에서 한 단어를 추가하면 작업의 50%가 추가될 수 있습니다.
- 인식 문제에는 보편적인 해결책이 없습니다. 단순히 "모든 비문을 인식"하는 알고리즘을 만들 수 없습니다. 거리의 간판과 한 장의 글은 근본적으로 다른 대상이다. 일반적인 알고리즘을 만드는 것이 가능할 수도 있지만(여기에 Google의 좋은 예가 있습니다) 이것은 대규모 팀의 많은 작업이 필요하고 수십 개의 서로 다른 서브루틴으로 구성됩니다.
- OpenCV는 많은 방법이 있고 거의 모든 문제의 50%를 해결할 수 있는 바이블이지만 OpenCV는 현실에서 할 수 있는 것의 작은 부분에 불과합니다. 한 연구에서는 "문제는 OpenCV 방법으로 해결되지 않으므로 해결할 수 없습니다."라는 결론으로 작성되었습니다. 이것을 피하고 게으르지 말고 OpenCV 템플릿을 사용하지 않고 매번 처음부터 현재 작업을 냉정하게 평가하십시오.
여기에 제시된 방법 목록은 완전하지 않습니다. 나는 내가 쓰지 않은 비판적 방법을 주석에 추가하고 각각에 2-3 개의 수반 단어를 부여할 것을 제안합니다.
파트 1. 필터링
이 그룹에서는 이미지를 분석하지 않고 이미지에서 관심 영역을 선택할 수 있는 방법을 배치했습니다. 이러한 방법의 대부분은 이미지의 모든 지점에 일종의 균일한 변환을 적용합니다. 필터링 수준에서는 이미지가 분석되지 않지만 필터링되는 지점은 특별한 특징이 있는 영역으로 간주될 수 있습니다.임계값 이진화, 히스토그램 영역 선택
가장 간단한 변환은 이미지를 임계값으로 이진화하는 것입니다. RGB 및 회색 음영 이미지의 경우 임계값은 색상 값입니다. 그러한 변환으로 충분한 이상적인 문제가 있습니다. 흰 종이에 있는 항목을 자동으로 선택한다고 가정합니다.
이진화가 발생하는 임계값의 선택은 주로 이진화 프로세스 자체를 결정합니다. 이 경우 이미지는 평균 색상으로 이진화되었습니다. 일반적으로 이진화는 임계값을 적응적으로 선택하는 알고리즘으로 수행됩니다. 이러한 알고리즘은 예상 또는 모드의 선택이 될 수 있습니다. 그리고 히스토그램의 가장 큰 피크를 선택할 수 있습니다.
이진화는 이미지가 RGB가 아니라 HSV인 경우를 포함하여 히스토그램으로 작업할 때 매우 흥미로운 결과를 제공할 수 있습니다. 예를 들어 관심 있는 색상을 분할합니다. 이 원리에 따라 라벨 검출기와 인체 피부 검출기를 모두 구축할 수 있습니다.
클래식 필터링: 푸리에, LPF, HPF
레이더 및 신호 처리의 기존 필터링 방법을 다양한 패턴 인식 작업에 성공적으로 적용할 수 있습니다. 순수한 형태의 이미지에서 거의 사용되지 않는 레이더의 전통적인 방법은 푸리에 변환(보다 구체적으로 FFT)입니다. 1D 푸리에 변환이 사용되는 몇 안 되는 예외 중 하나는 이미지 압축입니다. 이미지 분석의 경우 일반적으로 1차원 변환으로는 충분하지 않으므로 훨씬 더 리소스를 많이 사용하는 2차원 변환을 사용해야 합니다.
실제로 계산하는 사람은 거의 없습니다. 일반적으로 높음(HPF) 또는 낮음(LPF) 주파수로 선명해진 미리 만들어진 필터를 사용하여 관심 영역의 컨벌루션을 사용하는 것이 훨씬 빠르고 쉽습니다. 물론 이러한 방법은 스펙트럼 분석을 허용하지 않지만 특정 비디오 처리 작업에서 일반적으로 필요한 것은 분석이 아니라 결과입니다.
저주파(가우시안 필터)와 고주파(가버 필터)를 강조하는 필터의 가장 간단한 예입니다.
각 이미지 포인트에 대해 창이 선택되고 동일한 크기의 필터가 곱해집니다. 그러한 컨벌루션의 결과는 포인트의 새로운 값입니다. LPF 및 HPF를 구현할 때 다음 유형의 이미지를 얻습니다.
웨이블렛
그러나 신호와의 컨벌루션을 위해 임의의 특성 함수를 사용하면 어떻게 될까요? 그런 다음 "Wavelet 변환"이라고 합니다. 웨이블릿에 대한 이 정의는 올바르지 않지만 전통적으로 많은 팀에서 웨이블릿 분석은 이 패턴의 모델과 컨벌루션을 사용하여 이미지에서 임의의 패턴을 검색하는 것입니다. 웨이블릿 분석에 사용되는 일련의 고전적인 함수가 있습니다. 여기에는 Haar 웨이블릿, Morlet 웨이블릿, 멕시코 모자 웨이블릿 등이 포함됩니다. 내 이전 기사( , ) 중 여러 개가 있었던 Haar 프리미티브는 2차원 공간에 대한 이러한 함수를 참조합니다.
위는 고전적인 웨이블릿의 4가지 예입니다. 3D Haar 웨이블릿, 2D Meyer 웨이블릿, 멕시코 모자 웨이블릿, Daubechies 웨이블릿. 웨이블릿의 확장된 해석을 사용하는 좋은 예는 반짝임 자체가 웨이블릿인 눈에서 반짝임을 찾는 문제입니다.
고전적인 웨이블릿은 일반적으로 이미지 압축 또는 분류(아래에서 설명)에 사용됩니다.
상관관계
내가 웨이블릿을 자유롭게 해석한 후에는 실제 상관 관계를 언급할 가치가 있습니다. 이미지를 필터링할 때 필수 도구입니다. 고전적인 응용 프로그램은 오프셋 또는 광학 스트림을 찾기 위한 비디오 스트림 상관 관계입니다. 가장 단순한 시프트 검출기는 어떤 의미에서 차이 상관기이기도 합니다. 이미지가 상관되지 않는 곳에 움직임이 있었습니다.
함수 필터링
흥미로운 필터 클래스는 필터링 기능입니다. 이미지에서 간단한 수학 함수(선, 포물선, 원)를 감지할 수 있는 순전히 수학적인 필터입니다. 누적 이미지가 만들어지며 원본 이미지의 각 지점에 대해 이를 생성하는 함수 집합이 그려집니다. 가장 고전적인 변환은 직선에 대한 Hough 변환입니다. 이 변환에서 각 점 (x;y)에 대해 선 y=ax+b의 점 집합(a;b)이 그려지며, 이 경우 등식은 참입니다. 아름다운 사진을 얻으십시오:
(그림에서 캐치와 그러한 정의를 가장 먼저 찾아 설명하는 사람을위한 첫 번째 플러스, 여기에 표시된 것을 처음으로 말하는 사람을위한 두 번째 플러스)
Hough 변환을 사용하면 매개변수화할 수 있는 함수를 찾을 수 있습니다. 예를 들어 원. 모든 모양을 검색할 수 있는 수정된 변환이 있습니다. 이 변환은 수학자들이 몹시 좋아합니다. 그러나 이미지를 처리할 때 불행히도 항상 작동하는 것은 아닙니다. 매우 느린 속도, 이진화 품질에 대한 매우 높은 감도. 이상적인 상황에서도 다른 방법을 선호했습니다.
선에 대한 허프 변환의 상대는 라돈 변환입니다. 포인트가 많은 상황에서 성능 이득을 주는 FFT를 통해 계산됩니다. 또한 이진화되지 않은 이미지에도 적용할 수 있습니다.
윤곽선 필터링
별도의 필터 클래스는 테두리 및 윤곽선 필터링입니다. 경로는 이미지 작업에서 해당 이미지의 개체 작업으로 이동하려는 경우 매우 유용합니다. 객체가 매우 복잡하지만 잘 구별되는 경우 객체로 작업하는 유일한 방법은 윤곽선을 선택하는 것입니다. 윤곽선 필터링 문제를 해결하는 여러 가지 알고리즘이 있습니다.가장 일반적으로 사용되는 것은 잘 작동하고 OpenCV에서 구현되는 Kenny입니다(Sobel도 있지만 윤곽선을 더 잘 찾습니다).
기타 필터
위의 필터는 수정을 통해 작업의 80-90%를 해결하는 데 도움이 됩니다. 그러나 그 외에도 로컬 작업에 사용되는 더 드문 필터가 있습니다. 그러한 필터가 수십 개 있습니다. 모두 나열하지는 않겠습니다. 흥미로운 것은 반복 필터(예: 능동 모양 모델)와 라돈 변환 분야에서 고전적인 웨이블릿 필터링 및 분석의 합금인 ridgelet 및 curvlet 변환입니다. Beamlet 변환은 웨이블릿 변환과 논리 분석의 경계에서 아름답게 작동하여 윤곽을 강조할 수 있습니다.
그러나 이러한 변환은 매우 구체적이며 드문 작업에 맞게 조정됩니다.
Part 2. 필터링 결과의 논리적 처리
필터링은 처리에 적합한 데이터 세트를 제공합니다. 그러나 종종 이 데이터를 처리하지 않고 가져가서 사용할 수 없습니다. 이 섹션에는 이미지에서 개체의 속성 또는 개체 자체로 이동할 수 있는 몇 가지 고전적인 방법이 있습니다.형태
제 생각에는 필터링에서 논리로의 전환은 수학적 형태학( , , )의 방법입니다. 사실 이것은 이진 이미지를 늘리고 줄이는 가장 간단한 작업입니다. 이러한 방법을 사용하면 사용 가능한 요소를 늘리거나 줄여 이진 이미지에서 노이즈를 제거할 수 있습니다. 수학적 형태론을 기반으로 한 윤곽 알고리즘이 있지만 일반적으로 일종의 하이브리드 알고리즘이나 알고리즘을 결합하여 사용합니다.
윤곽 분석
필터링 섹션에서 경계를 얻는 알고리즘에 대해 이미 언급했습니다. 결과 경계는 매우 간단하게 윤곽으로 변환됩니다. Canny 알고리즘의 경우 이는 자동으로 발생하며 다른 알고리즘의 경우 추가 이진화가 필요합니다. 예를 들어 딱정벌레 알고리즘을 사용하여 이진 알고리즘의 윤곽선을 얻을 수 있습니다.윤곽선은 개체의 고유한 특성입니다. 이를 통해 종종 윤곽선을 따라 개체를 식별할 수 있습니다. 이것을 가능하게 하는 강력한 수학적 장치가 있습니다. 이 장치를 등고선 분석( , )이라고 합니다.
솔직히 말해서 실제 문제에 윤곽 분석을 적용한 적이 없습니다. 너무 이상적인 조건이 필요합니다. 경계가 없거나 노이즈가 너무 많습니다. 그러나 이상적인 조건에서 무언가를 인식해야 하는 경우 윤곽 분석이 훌륭한 옵션입니다. 그것은 매우 빠르고 아름다운 수학 및 이해하기 쉬운 논리를 작동합니다.
특이점
키포인트는 개체가 자체 또는 유사한 개체 클래스와 연결될 수 있도록 하는 개체의 고유한 특성입니다. 이러한 점을 선택하는 데는 수십 가지 방법이 있습니다. 일부 방법은 인접한 프레임의 특수 지점을 강조 표시하고, 일부는 오랜 시간이 지난 후 조명이 변경될 때 객체가 회전하는 경우에도 남아 있는 특수 지점을 찾을 수 있도록 합니다. 그다지 안정적이지 않지만 빠르게 계산되는 특수 지점을 찾을 수 있는 방법부터 시작하여 점점 더 복잡해질 것입니다.1학년. 몇 초 동안 안정적인 특이점.이러한 점은 인접한 비디오 프레임 사이에서 개체를 안내하거나 인접한 카메라의 이미지를 수렴하는 데 사용됩니다. 이러한 지점에는 이미지의 로컬 최대값, 이미지의 모서리(최고의 검출기, 아마도 Haris 검출기), 분산 최대값에 도달하는 지점, 특정 기울기 등이 포함됩니다.
이급. 물체의 조명과 작은 움직임을 변경할 때 안정적인 특이점.이러한 포인트는 주로 개체 유형의 교육 및 후속 분류에 사용됩니다. 예를 들어, 보행자 분류기 또는 얼굴 분류기는 그러한 지점에 구축된 시스템의 산물입니다. 앞서 언급한 웨이블릿 중 일부는 이러한 포인트의 기초가 될 수 있습니다. 예를 들어, Haar 프리미티브, 눈부심 검색, 다른 특정 기능 검색. 이러한 점에는 HOG(방향 기울기의 히스토그램) 방법으로 찾은 점이 포함됩니다.
병종. 안정적인 포인트.나는 완전한 안정성을 제공하는 두 가지 방법과 그 수정에 대해서만 알고 있습니다. SURF와 SIFT입니다. 이미지를 회전해도 핵심 포인트를 찾을 수 있습니다. 이러한 포인트의 계산은 다른 방법보다 오래 걸리지만 시간이 다소 제한됩니다. 불행히도 이러한 방법은 특허를 받았습니다. 러시아에서는 특허 알고리즘이 불가능하므로 국내 시장에 사용하십시오.
파트 3. 교육
이야기의 세 번째 부분은 이미지와 직접적으로 작동하지 않지만 결정을 내릴 수 있는 방법에 대해 설명합니다. 기본적으로 이들은 기계 학습 및 의사 결정의 다양한 방법입니다. 최근에 Yandyks는 Habr에 이 주제에 대한 과정을 게시했는데 거기에는 아주 좋은 선택이 있습니다. 여기는 텍스트 버전입니다. 주제에 대한 진지한 연구를 위해 그것들을 볼 것을 강력히 추천합니다. 여기서는 특히 패턴 인식에 사용되는 몇 가지 기본 방법을 식별하려고 노력할 것입니다.상황의 80%에서 인식 문제에서 학습의 본질은 다음과 같습니다.
여러 개체 클래스가 있는 테스트 샘플이 있습니다. 사진 속 사람의 존재/부재가 되게 하십시오. 각 이미지에는 Haar, HOG, SURF 또는 일부 웨이블릿과 같은 일부 기능으로 강조 표시된 기능 세트가 있습니다. 학습 알고리즘은 새로운 이미지를 분석하고 이미지에 있는 객체를 결정할 수 있는 모델을 구축해야 합니다.
어떻게 됐어? 각 테스트 이미지는 기능 공간의 한 지점입니다. 좌표는 이미지에 있는 각 기능의 가중치입니다. 우리의 기호를 "눈의 존재", "코의 존재", "두 손의 존재", "귀의 존재" 등으로 합시다. 우리는 이 모든 기호를 우리가 가지고 있는 탐지기로 할당할 것입니다. 인간과 유사한 신체 부위에 훈련된 그러한 공간에 있는 사람에게 올바른 점은 입니다. 원숭이의 경우 말의 경우 점을 찍으십시오. 분류기는 예제 샘플에 대해 훈련됩니다. 그러나 모든 사진이 손을 보여주지는 않았고, 다른 것들은 눈이 없었고, 세 번째 사진은 분류기 오류로 인해 원숭이가 사람의 코를 가졌습니다. 학습 가능한 인간 분류기는 다음과 같은 방식으로 기능 공간을 자동으로 분할합니다. 첫 번째 기능이 0.5 범위에 있는 경우
많은 분류기가 있습니다. 그들 각각은 일부 작업에서 더 잘 작동합니다. 특정 작업에 대한 분류기를 선택하는 작업은 대체로 예술입니다. 다음은 주제에 대한 멋진 사진입니다.
간단한 경우, 1차원 분리
특징 공간이 1차원이고 2개의 클래스를 분리해야 하는 가장 간단한 분류 사례를 예로 들어 보겠습니다. 이러한 상황은 생각보다 자주 발생합니다. 예를 들어 두 신호를 구분하거나 패턴을 샘플과 비교해야 하는 경우입니다. 학습 샘플이 있다고 가정해 보겠습니다. 이 경우 X축은 유사성의 척도가 되고 Y축은 그러한 척도가 있는 이벤트의 수가 되는 이미지를 얻습니다. 원하는 객체가 자신과 유사하면 왼쪽 가우시안을 얻습니다. 유사하지 않은 경우 - 맞습니다. 값 X=0.4는 잘못된 결정이 잘못된 결정을 내릴 확률을 최소화하도록 샘플을 분리합니다. 분류 작업은 이러한 구분 기호를 찾는 것입니다.
작은 메모. 오류를 최소화하는 기준이 항상 최적인 것은 아닙니다. 아래 그래프는 실제 홍채인식 시스템의 그래프입니다. 이러한 시스템의 경우 대상에 대한 외부인의 잘못된 승인 가능성을 최소화하는 방식으로 기준이 선택됩니다. 이러한 확률을 "제1종 오류", "거짓 경보 확률", "거짓 긍정"이라고 합니다. 영어 문헌에서 "잘못된 액세스 비율".
) AdaBusta는 가장 일반적인 분류기 중 하나입니다. 예를 들어 Haar 캐스케이드가 그 위에 구축됩니다. 일반적으로 이진 분류가 필요할 때 사용되지만 더 많은 수업을 위한 교육을 방해하는 것은 없습니다.
SVM ( , , , ) 구현이 많은 가장 강력한 분류기 중 하나입니다. 원칙적으로 내가 만난 학습 과제에서는 아다부스타와 비슷하게 작동했다. 상당히 빠른 것으로 간주되지만 훈련이 Adabusta보다 어렵고 올바른 커널을 선택해야 합니다.
신경망과 회귀도 있습니다. 그러나 그것들을 간단히 분류하고 그것들이 어떻게 다른지 보여주기 위해서는 이것보다 훨씬 더 긴 기사가 필요합니다.
________________________________________________
수학 및 설명에 뛰어들지 않고 사용된 방법에 대한 간략한 개요를 제공할 수 있었으면 합니다. 아마도 이것은 누군가를 도울 것입니다. 물론이 기사는 불완전하고 스테레오 이미지 작업, Kalman 필터를 사용한 LSM 또는 적응 베이지안 접근 방식에 대한 단어가 없습니다.
기사가 마음에 드시면 기존 ImageRecognition 문제를 해결하는 방법에 대한 몇 가지 예를 선택하여 두 번째 부분을 만들어 보겠습니다.
그리고 마지막으로
무엇을 읽을까요?1) 한때 B. Yana의 "Digital Image Processing"이라는 책이 정말 마음에 들었습니다. 이 책은 간단하고 명확하게 쓰여졌지만 동시에 거의 모든 수학이 제공됩니다. 기존 방법에 익숙해지는 데 좋습니다.
2) 장르의 고전은 R Gonzalez, R. Woods "Digital Image Processing"입니다. 왠지 첫 번째 것보다 나에게 더 어려웠습니다. 수학은 훨씬 적지만 방법과 그림은 더 많습니다.
3) "머신 비전 문제의 이미지 처리 및 분석" - PhysTech 부서 중 하나에서 가르치는 과정을 기반으로 작성되었습니다. 많은 방법과 자세한 설명. 그러나 제 생각에는 이 책에는 두 가지 큰 단점이 있습니다. 이 책은 함께 제공되는 소프트웨어 패키지에 중점을 두고 있으며, 책에서 간단한 방법에 대한 설명이 너무 자주 수학적 정글로 바뀌어 꺼내기가 어렵습니다. 방법의 구조 다이어그램. 그러나 저자는 거의 모든 콘텐츠가 제공되는 편리한 사이트인 wiki.technicalvision.ru를 만들었습니다.
4) 왠지 이미지 인식과 기계 학습을 할 때 떠오르는 세상의 그림을 구조화하고 연결하는 좋은 책은 Jeff Hawkins의 "On Intelligence"인 것 같습니다. 다이렉트 방식은 없지만, 다이렉트 이미지 처리 방식은 어디서 오는 건지 생각해볼 여지가 많다. 이해하면 이미 인간 두뇌의 방법을 보았지만 비디오 처리 작업에 있음을 이해합니다.
우리가 3차원 장면을 2차원 이미지로 볼 때(그림, 사진, 모니터 화면에서), 우리가 인생에서 같은 장면을 직접 관찰했다면 볼 수 있었던 모든 대상이 직접적으로 존재하는 것처럼 보입니다. 거기. 한편, 2차원 이미지로 우리에게 실제로 주어지는 모든 것은 보이는 필드, 이는 단지 일부 밝기 분포 기능또는 그림 물감 2차원 평면에서: 에프(엑스, 와이) , 어디 엑스그리고 와이이미지 평면을 설명하는 데카르트 좌표입니다.
또한 컴퓨터 모니터의 화면에 가까이 가면 화면의 이미지가 실제로 매끄럽고 연속적이지 않고 규칙적인 직사각형 매트릭스에 배열된 개별 색상의 직사각형으로 구성된 개별 "모자이크"임을 알 수 있습니다. 이것은 디지털 이미지입니다. 수학적 관점에서 디지털 이미지크기(DimXDimY)의 2차원 행렬입니다. 여기서 x는 행렬 행의 요소 번호를 설명하는 0에서 DimX-1까지의 정수이고, y는 행을 설명하는 0에서 DimY-1까지의 정수입니다. 이 요소가 있는 행렬의 번호입니다. 동시에 디지털 이미지 자체의 요소(사각형 매트릭스의 셀)를 호출합니다. 픽셀(픽셀, 그림 요소). 가장 간단한 경우, 각 픽셀(Im)은 휘도 분포 함수의 값에 비례하는 정수 스칼라 값을 가집니다. 에프(엑스, 와이) 평면의 특정 지점에서.
무화과에. 그림 1.1.1에서 왼쪽은 이미지로 렌더링된 여성의 얼굴 이미지, 오른쪽은 같은 얼굴(오른쪽 눈)의 이미지를 확대한 부분으로, 이미지의 각 요소는 해당 숫자 픽셀 값. 이미지의 밝은 요소는 b에 해당합니다. 영형매트릭스의 큰 값, 어두운 값 - 작은 값. 디지털 이미지에는 다른 정보가 포함되어 있지 않습니다.
@쌀. 1.1.1 2차원 강도 매트릭스로서의 디지털 이미지
머신 비전을 연구하기 시작하면 한 형식 또는 다른 형식의 2차원 숫자 배열만이 컴퓨터에 디지털 이미지로 저장된다는 점을 명확하게 이해해야 합니다. 이미지에서 추출하려는 다른 데이터(모양, 선, 개체, 치수, 표시된 텍스트의 내용 등)는 여러 이미지 처리 및 분석을 적용한 결과로만 얻을 수 있습니다. 우리가 직접 프로그래밍하거나 잘 알려진 이미지 분석 소프트웨어 패키지에서 사용할 수 있는 기성 절차를 사용해야 합니다. 동시에 컴퓨터 비전의 간단한 문제를 해결하기 위해 기성 도구는 이미지 처리 절차의 표준 라이브러리에서 찾을 가능성이 높으며 더 복잡한 문제를 해결하려면 특정 기성 절차를 결합해야 합니다. 인간의 "생물학적" 시각이 쉽게 그리고 힘들이지 않고 해결하는 많은 "일상적인" 작업들, 컴퓨터 머신 비전은 여전히 해결책이 없고 계속해서 그것들을 찾고 있습니다. 결국, 그의 자연스러운 시력을 사용하여 사람은 어떤 환경에서도 쉽게 탐색하고, 물체를 인식하고, 경로를 선택하고, 자동차를 운전하는 등 훨씬 더 많은 일을 합니다. 비디오 카메라에서 이미지를 수신하는 컴퓨터가 이 모든 작업을 수행할 수 없는 이유는 무엇입니까? 인간의 눈의 구조일까요?
사실 인간의 눈은 비디오 카메라와 마찬가지로 디지털 이미지와 유사한 "보이는 필드"만 형성합니다. 이 경우 동공과 수정체로 구성된 광학 시스템은 2차원 이미지를 망막에 투사하며, 여기에서 감광성 세포("간상체" 및 "원추체")가 결과 이미지를 신경 임펄스로 변환합니다. 그 후에야 뇌의 해당 부서에서 기능하는 수신된 정보를 처리하는 복잡한 메커니즘이 이러한 충동을 우리가 이해할 수 있는 보이는 장면의 이미지로 해석합니다. 따라서 인간에서 "시력"의 기능은 눈뿐만 아니라 "눈 + 뇌"( "센서 + 컴퓨터") 시스템에 의해 수행됩니다. 사람이 자신이 보는 것을 이해할 수 있게 해주는 것은 뇌에 내장된 정보 처리 알고리즘입니다. 이러한 기본 제공 알고리즘의 역할은 다음 예에서 설명할 수 있습니다.
20세기 중반에 안과 의사들이 눈의 수정체 수술을 배웠을 때, 선천적으로 맹인인 많은 사람들이 선명하게 볼 수 있는 기술적 능력을 갖게 되었습니다. 즉, 지금까지 맹인이었던 사람에게 그러한 수술을 한 후 (단순히 빛이 렌즈를 통과하지 못함) 망막에 이미지가 형성되기 시작했고 해당 신호가 발생하는 것과 똑같은 방식으로 뇌에 들어가기 시작했습니다. 건강한 사람들에게서. 불행하게도 이 경우 "빛을 본다"는 것은 "보기 시작하다"를 의미하지 않습니다. 후속 역사에서 알 수 있듯이 "기술적으로 깨달은"성인 환자의 대다수는 시야에서 단순한 기하학적 모양을 인식하는 것보다 더 중요한 결과를 얻을 수 없었습니다. 심지어 이것은 그들로부터 심각한 의식적 노력이 필요했습니다. 공간에서 얼굴과 방향으로 사람을 인식하는 것은 여전히 그들에게 압도적인 과제였습니다. 사실 어린 시절 사람들에게서 발달하는 "자동" 시각 분석의 내장 메커니즘은 이 환자들에게서 적시에 개발되지 않았고, 그들은 이미지 입력 장치가 있는 컴퓨터의 위치에 있음을 발견했습니다. 그러나 그의 분석에 필요한 소프트웨어가 없습니다.
숫자 데이터의 2차원 배열인 이미지를 분석하는 작업의 복잡성을 최종적으로 확인하기 위해 추상적인 숫자를 다루는 컴퓨터 프로그램을 대신해 보겠습니다. 이를 위해 이미지 인식의 양식을 정신적으로 변경합시다. 시각적 영역에서 촉각 영역으로 옮길 것입니다. 크기가 이미지 크기 (DimXDimY)와 같은 바둑판으로 강도 값의 2 차원 배열을 상상해 봅시다. 각 셀의 중앙에는 높이가있는 열이 붙어 있습니다. 해당 이미지 픽셀의 값에 비례합니다. 즉, 2차원 이미지를 일종의 조건부 3차원 표면으로 간주합니다. 무화과에. 1.1.2 왼쪽은 여성의 얼굴 조각을 이미지로, 오른쪽은 유사 입체부조로 표현한 것이다.
@쌀. 1.1.2. 의사 3D 부조로서의 디지털 이미지
이제 이미지를 보지 않고 이미지에 해당하는 "부조"를 느끼고 집, 개 또는 인간의 눈과 같이이 "부조"가 정확히 무엇을 묘사하는지 결정해야한다고 상상해보십시오. 실험에서 알 수 있듯이 평범한 사람은 그러한 작업에 대처할 수 없습니다. 이러한 "릴리프" 표현에서 가장 단순한 기하학적 모양을 인식하는 것조차도 상당한 노력과 관련이 있으며 특별한 기술, 전략 및 촉진 알고리즘의 의식적인 개발이 필요합니다. 이것은 "디지털 이미지" 개체의 명백한 단순성에도 불구하고 컴퓨터 및 머신 비전 작업의 진정한 복잡성입니다.
UDC 004932:621.396
T.M. VLASOVA, V.G. 칼미코프
디지털 라인의 세그먼트 시퀀스로서 이미지 윤곽을 인식하기 위한 알고리즘 및 프로그램
초록: 주어진 작업에서 이진 이미지의 윤곽선에서 디지털 직선 세그먼트를 인식하는 알고리즘과 알고리즘의 소프트웨어 구현이 고려됩니다. 이미지를 처리하기 위해 이 알고리즘을 사용하면 기존의 이미지 설명 방법에 비해 보다 자연스럽고 경제적인 설명이 가능합니다. 고려한 알고리즘 및 소프트웨어 구현은 하프톤 및 컬러 이미지를 처리할 때 윤곽선 설명에도 사용할 수 있습니다.
키워드: 이미지, 윤곽선, 디지털 직선 세그먼트, 알고리즘, 프로그램.
주석: 이 로봇에서는 이진 이미지의 윤곽선에서 디지털 선을 인식하는 알고리즘과 알고리즘의 소프트웨어 구현이 도입되었습니다. 우리는 이미지의 코딩 방법과 이미지의 묘사가 보다 자연스럽고 경제적으로 동일할 정도로 이미지를 처리하는 알고리즘을 개발했습니다. 제안된 알고리즘 및 소프트웨어 구현은 나브톤 및 컬러 이미지를 처리할 때 윤곽 코딩을 위해 설정할 수 있습니다. 키워드: 이미지, 윤곽선, 디지털 직선, 알고리즘, 프로그램.
개요: 이 논문에서는 이진 이미지의 윤곽선에서 디지털 선의 세그먼트를 인식하는 알고리즘과 알고리즘의 소프트웨어 구현을 고려합니다. 이미지 처리에 이 알고리즘을 사용하면 기존의 방법에 비해 이미지를 더 자연스럽고 경제적으로 표현할 수 있습니다. 고려된 알고리즘 및 소프트웨어 구현은 그레이스케일 및 컬러 이미지 처리에서 윤곽선을 설명하는 데에도 사용할 수 있습니다. 키워드: 이미지, 윤곽선, 디지털 라인 세그먼트, 알고리즘, 프로그램.
1. 소개
일련의 직선 세그먼트 및 곡선 호로 이미지 윤곽의 구조 분석은 인공 지능 시스템에서 해석을 목적으로 하는 이미지 처리의 주요 작업 중 하나입니다.
대부분의 경우 이미지는 이미지의 배경과 개체를 결정하는 광학 밀도, 색상, 질감과 같은 일부 법칙에 따라 일정하거나 변경되는 매개 변수가 있는 영역으로 분할된 평면의 일부로 간주될 수 있습니다. 이러한 각 영역의 필수 속성은 경계입니다. 즉, 윤곽선은 선분과 곡선 호로 구성된 단순하게 연결된 시퀀스입니다. 래스터 이미지를 처리할 때 일반적으로 개체의 윤곽이 강조 표시됩니다. 그러나 별도의 경계 픽셀 집합으로 표시되는 개체의 윤곽은 기하학적 본질을 충분히 표현하지 못하기 때문에 추가 처리에 적합하지 않습니다.
일련의 선분 형태로 이미지 윤곽을 인식하는 것은 래스터 이미지를 처리하는 과정에서 주요 작업 중 하나로 간주될 수 있습니다. 윤곽선을 일련의 직선 세그먼트로 표현하는 문제를 해결하면 인간의 인식에 자연스럽고 아핀 변환에서 불변하며 특히 신경망 처리에 편리한 간결한 형태로 이미지 설명을 얻을 수 있습니다. 선분은 컨투어의 기본 요소입니다. 곡선의 호는 미적분학의 기초와 많은 실제 응용 분야에서 종종 그 안에 새겨진 파선으로 대체됩니다.
알려진 방법 및 알고리즘, 특히 작업에서 제안된 방법 및 알고리즘은 모든 응용 프로그램에 허용되지 않는 근사 솔루션을 얻을 수 있도록 합니다.
이 논문에서는 정보 손실 없이 디지털 직선의 세그먼트 시퀀스로 이진 이미지의 윤곽을 인식하는 것을 고려합니다.
2. 일련의 디지털 라인 세그먼트로서의 컨투어
이 절에서는 영상 윤곽의 구조적 분석을 디지털 곡선의 호와 디지털 선의 세그먼트로 윤곽을 분할하기 위한 초기 데이터인 디지털 선의 세그먼트 시퀀스로 간주합니다.
객체가 경계 윤곽에 의해 완전히 결정되는 이진 이미지에 대해 살펴보겠습니다. 디지털 곡선의 호와 디지털 선의 세그먼트는 직선의 세그먼트와 곡선의 호로 형성된 윤곽선을 포함하는 이미지를 샘플링하여 형성됩니다.
직선 세그먼트 및 곡선 호의 특징적인 특징은 변환 중에 손실됩니다. 샘플 이미지를 충분한 배율로 볼 때 시퀀스에서 개별 선분과 곡선의 호를 인식하기 어려운 경우가 많습니다.
수직 및 수평 섹션. 윤곽선(두께가 없는 수학적 선)이 픽셀의 연결된 시퀀스, 즉 두께가 있는 시각적 선으로 모니터 화면에 표시된다는 사실로 인해 처리 중에 추가적인 어려움이 발생합니다.
여기서 발생하는 문제를 제거하기 위해 이산화 결과 원본에서 얻은 이미지를 2차원 셀 복합체로 간주하겠습니다. 이 경우
픽셀은 이 세포 복합체의 2차원 요소입니다. 픽셀 외에도 균열과 점이 있습니다. 크랙은
1차원 요소인 픽셀의 측면. 도트는 크랙의 끝점과 픽셀의 꼭지점입니다. 점은 0차원 요소입니다. 그래서
따라서 고려 중인 경우 객체의 윤곽은 객체의 픽셀과 배경 사이의 경계를 이루는 윤곽 균열의 연결된 폐쇄 시퀀스입니다. 등고선은 일련의 정수 점 좌표로 설명할 수 있습니다.
윤곽 균열 제한. 에 표시된 것처럼 이미지 평면의 표현은 다음과 같습니다.
세포 복합체는 많은 이점을 제공합니다. 특히 영역 경계는 면적이 0인 가는 곡선이 됩니다.
무화과에. 그림 1은 곡선의 호와 직선 세그먼트로 형성된 객체의 초기 윤곽선과 일련의 크랙과 같은 디지털 등가물의 예를 보여줍니다. 서로 다른 방향의 균열에 속하는 점에 번호가 매겨져 있습니다. 작업에서와 같이 b-요소는 특정 지점에서 시작하여 동일한 또는 수직 방향의 균열로 끝나는 동일한 방향의 연결된 일련의 균열을 의미합니다. 무화과에. 1은 윤곽선을 b 요소로 분할할 수 있는 것 중 하나를 보여줍니다. 이 요소는 (0-2), (2-4), (4-6), (6-8), (8) 지점 사이의 균열에 의해 형성됩니다. -9), (9 -11), (11-13), (13-15), (15-17), (17-19), (20-21), (21-23), (23-25) ), (25-27), (27-0). 각 b 요소는 다음 매개 변수로 특징 지어집니다. 초기 점 g에 대한 방향 (g = 0 - 위쪽 방향, 1 - 오른쪽, 2 - 아래쪽, 3 - 왼쪽); l - 방향 g의 균열 수(! = 1,2,...); 이전 균열의 g 방향에 대한 마지막 균열 q의 방향(q = -1 - 마지막 균열은 g 방향에 대해 왼쪽으로, +1 - 오른쪽으로, 0 - g 방향과 일치함 ). 크랙 수 l은 일반적으로 b-요소의 "길이"라고 합니다. b-요소(0-2)의 경우 g =0, !=3, q =+1입니다. b-요소(27-0)의 경우 g =3, =1, q =0.
컨투어에서 디지털 라인의 세그먼트를 선택하는 방법은 세그먼트를 형성하는 b-요소 시퀀스의 다음 속성을 사용합니다. 이러한 시퀀스에는 동일한 값 g, q를 가진 b 요소가 포함됩니다. 길이는 !, +1 값을 갖습니다. 그리고
길이 !, +1의 b-요소의 교번은 정수 n = Ax = |x1 - x2|를 나누어 얻은 연속 분수로 결정됩니다. 및 m = Ay = |y1 - y2\, 여기서 (x1zy1), (x2,y2)는 초기의 좌표입니다.
및 세그먼트의 끝점: 또는
명확하게 하기 위해 n > m으로 가정합니다.식 (1)에서 다음과 같이 n을 m으로 나눈 정수 부분인 l은 디지털 직선의 세그먼트에서 같은 방향의 l개의 연속 균열 수에 해당합니다. 인접한 수직 균열과 함께 길이의 b 요소를 형성합니다!. 길이가 l인 b-요소 k1개와 길이 !+1인 b-요소 하나(또는 길이 +1인 b-요소 k1개와 길이가 b-요소 하나!)는 "길이" k1인 K1-요소를 형성합니다. "길이" b-요소와 유사). 연속된 b-요소와 길이가 1씩 다른 b-요소는 주어진 K1-요소의 수정된 b-요소라고 합니다. 유사하게, "길이" k1의 k2 연속 K1-요소 및 "길이" k1+1의 하나의 K1-요소(또는 "길이" k1+1의 k2 연속 K1-요소 및 "길이" k1의 하나의 K1-요소)는 다음을 형성합니다. K2- "길이" 요소 k1. 그래서
k + k 2 + k z + ... + kg
계속되는 분수의 구성원이 소진될 때까지 더 나아가십시오. K1 -element(일반적으로 K-1 -element)는 연속된 K1 -element(Kg-1 -element)와 길이가 1씩 다른데, 이를 K2 -의 변형된 K1 -element(Kg-1 -element)라고 부르겠습니다. 요소(Kg -요소). 그리하여 각각에게
직선의 디지털 세그먼트는 이 세그먼트의 구조를 결정하는 요소인 연속 분수에 해당합니다.
그림의 윤곽선에서 1에서 디지털 라인의 다음 세그먼트를 선택할 수 있습니다: 0-3, 3-9, 910, 10-17, 17-0.
3. 컨투어에서 디지털 라인 세그먼트 선택
이미지 윤곽, 특히 이진 이미지를 처리할 때 윤곽을 형성하는 일련의 균열에서 라인 세그먼트를 형성하는 시퀀스 부분을 선택해야 합니다. 이 문제는 등고선의 L 요소 시퀀스에서 연속된 분수의 요소를 결정하는 문제로 간주할 수 있습니다. 이 문제는 선분의 시작점과 끝점의 좌표 차이의 비율로 구한 연속된 분수의 구성원 시퀀스로 직선의 선분 구조를 결정하는 문제와 반대입니다.
디지털 라인의 세그먼트를 선택하는 방법은 다음 작업을 순차적으로 수행하는 것입니다.
1. 균열 순서에서 b-요소 순서 선택. 이 작업은 정수 부분의 정의에 해당합니다! 연속 촬영(1).
2. b-요소의 시퀀스에서 r = 1인 Kg-요소 시퀀스의 분리 및 각 K1-요소의 b-요소 중 하나는 다른 것보다 크거나 작은 1개의 균열을 포함해야 합니다. 이 동작은 연속된 분수(1)의 k1 번째 요소의 정의에 해당합니다. 실행 후 r 값을 1씩 증가시켜야 합니다.
3. Kg-1-요소의 순서에서 Kg-요소의 순서의 분리,
또한 각 Kg 원소의 Kg-1 원소 중 하나는 다른 것보다 많거나 적은 K-2 원소를 하나씩 포함해야 합니다. 이 작업은 연속된 분수(1)의 k(-번째 요소의 정의에 해당합니다. 실행 후 r 값을 1씩 증가시켜야 합니다.
4. 연속된 Kr-요소에서 여전히 가능할 때까지 3항을 반복합니다.
Km 요소를 형성합니다.
5. 동일한 Kg-요소에 포함되지 않은 두 개의 인접한 b-요소 사이의 경계 지점이 결정됩니다. 이러한 점은 윤곽선을 형성하는 디지털 선분의 끝점입니다.
b-요소 시퀀스에서 선분을 선택하는 알고리즘을 고려하십시오.
Let [b5 (/5,gs,qs)); s = 0.1,...,t - 윤곽선을 형성하는 L-요소의 시퀀스; x5, y5 - e번째 b 요소의 시작 좌표. [hu, y y); y = ; r = 0,1,...,!; !< £ - множество
윤곽 중단점. 중단점은 경로를 형성하는 선분의 끝점을 정의합니다. 중단점을 찾는다는 것은 윤곽선을 형성하는 선분을 결정하는 것을 의미합니다.
고려 중인 각 세그먼트는 Kg 요소와 체인으로 특징지어집니다.
발사. 세그먼트 인식의 초기 순간에 해당 연속 분수의 요소는 0과 같습니다. 순서 r 및 요소 값을 포함하여 Kr 요소의 매개 변수가 인식되면 세그먼트가 인식된 것으로 간주할 수 있습니다. 해당 연속 분수.
1. 초기 조건.
시퀀스 [b5(/5, gs, qs)) 및 (x5, y5)가 제공됩니다.
중단점의 좌표를 찾아야 합니다 |x;.,y,).
k0r:= 0, k1r:= 0, k2r:= 0,..., kr:= 0 - 연속 분수 요소의 작동 값.
첫 번째 세그먼트의 시작점으로 점 5 =0을 취합시다. i=0; i=0.
2. 첫 번째 직선 세그먼트의 시작 부분에서 시퀀스의 첫 번째 b-요소를 가져옵니다. 시작점은 x5,y입니다. 길이 /=/0은 연속된 분수의 첫 번째 요소 값이기도 합니다.
5:=5+1; k1p:=k1p+1.
3. 다음 b-요소가 이전 요소와 함께 K0-요소를 형성하는지 확인하십시오.
3.1. ((q3 == q3-1) && (q3 == 73-1)&& (4 == /3-1))이면 Kr-요소 k0p:= k0p +1의 연속; 5:= 5 + 1; 그리고 선분의 연속. 항목 3으로 이동합니다.
3.2. ((d3 f d3-1) || (d3 f 73-1)11 (|/e - /є-1!>1))이면 선분의 끝입니다. 항목 5로 이동합니다.
3.3. 만약 ((&== 93+1) && (%== 73+1)&& ((/3+1== /3+1)1! (/3 - 1 == /3+1))), 그런 다음 K0 요소의 완료; Ї = Ї+1.
4. K(-요소.
4.1. (k == 0)이면 k ^= k^; cr:= 0; k^1p:= k1+ 1p+1; 5:=5 +1; Km 요소의 시작.
항목 3으로 이동합니다.
4.2. ((k IF 0)&&(k == k^))이면 k^1p:= k^1p+1; 5:= 5+1; Ki+1 요소의 연속. 항목 3으로 이동합니다.
4.3. ((k (Ф 0)&&((k+1== k1p)11(k1-1 == k^)))이면 Ї := +1; Km 요소의 끝.
항목 4로 이동합니다.
4.4. ((^φ0)&&(|k - k1p|>1))인 경우 세그먼트의 끝은 항목 5로 직접 전환됩니다.
5. 세그먼트의 끝.
X] = X들; y \u003d Uz; k1p:= 0, k2p:= 0,., kіp:= 0; k:= 0, k2:= 0,., k:= 0.
만약 (들< S), то s:= s +1; переход к п. 2.
그렇지 않으면 L 요소 시퀀스의 끝입니다. 알고리즘의 끝.
실제로 제안된 알고리즘은 연속된 분수의 요소와 획득된 각 Kt 요소에 대해 새로 구성된 Kt -요소의 연속된 분수가 이미 구성된 Kt 요소에 적합한지 확인합니다.
4. 디지털 라인의 세그먼트를 선택하는 프로그램
알고리즘 설명에서 알 수 있듯이 상당한 수의 조건부 점프가 포함되어 있으며 프로그램 디버깅시 발생하는 어려움으로 인해 구조적 프로그래밍의 권장 사항과 모순됩니다. 또한 사전에 매개변수 Kt의 개수를
변수 t가 미리 제한되지 않았기 때문에 결정할 수 없습니다. t 값 제한
이것은 미리 이미지의 크기를 제한하는 것을 의미합니다. 소프트웨어 구현, 특히 사소한 수단에 의한 제안된 알고리즘의 디버깅은 표시된 이유로 상당히 어렵습니다. 최신 객체 지향 프로그래밍 도구를 사용하면 소프트웨어 구현을 개발하고 디버깅하는 어려움을 줄일 수 있습니다.
제안된 알고리즘은 Visual C++ 환경에서 이미지 처리를 위한 실험실 소프트웨어 패키지의 일부인 LINESEGM 프로그램의 형태로 구현됩니다.
초기 정보로 LINESEGM 프로그램은 처리된 이미지의 각 윤곽에 대해 구축된 L 요소 시퀀스를 사용합니다.
프로그램의 결과는 세그먼트 끝점의 좌표로 표시되는 각 윤곽선에 대해 구성된 디지털 직선 세그먼트의 연결된 시퀀스입니다.
알고리즘에서 알 수 있듯이 Kt-l -elements에서 Kt -elements를 구성하는 연산은
t의 모든 값에 대해 동일합니다. 초기 값 t=0은 알고리즘이 실행될 때마다 1씩 증가한다는 점에 유의하십시오.특수 클래스 CKForLn에는 알고리즘의 연산에 해당하는 메서드가 포함됩니다. 알고리즘을 구현하는 프로그램이 작동하는 동안 t가 1씩 증가할 때마다 t의 각 값에 대해 알고리즘 연산을 수행하는 함수를 포함하는 새 객체가 생성됩니다.
제로 레벨에서 K0 요소는 K 요소가 아니라 L -
제로 레벨에서 알고리즘을 구현하기 위해 CKForLn 클래스인 Cmini 클래스의 특수 수정인 요소가 생성되었습니다.
프로그램 작동 원리는 t의 각 값에 대해 프로그램이 Kt 요소의 매개변수를 결정하는 함수를 포함하는 t-번째 수준의 CKForLn 클래스 개체를 구현한다는 것입니다. Kt-요소의 초기 매개변수는 이미 매개변수입니다.
매개변수가 CKForLn t-1 클래스의 개체에 의해 정의된 완성된 Kt-l 요소
와우 수준.
CKForLn 클래스의 개체는 조건이 발생할 때 구현됩니다. 즉, 다음 수준의 K 요소를 빌드해야 할 필요성이 있으며 특수 동적 배열에 누적됩니다. 0 수준 개체는 프로그램 시작 시 즉시 생성됩니다.
t가 증가함에 따라 동적 배열에 개체를 구현하면 이미지 크기에 제한을 두지 않아도 됩니다. 이미지 크기 제한은 사용 중인 컴퓨터의 리소스에 의해서만 결정됩니다.
프로그램의 동작을 설명할 때 완성된 Kt의 개념을 사용합니다.
요소. 완성된 각 Kt 요소는 kt Kt-l 요소와 kt-l ±1 Kt-2 요소를 포함하는 하나의 수정된 Kt-l 요소를 포함합니다. 이는 불완전한 Kt 요소를 포함하지 않는 불완전한 Kt 요소와 다릅니다.
CKForLn 클래스에는 다음 메서드가 포함됩니다.
1. Method DK(), (define K-element) - K-element를 정의합니다.
Kt 요소를 결정한다는 것은 주어진 Kt 요소를 형성하는 Kt-1 요소의 수를 결정하는 것을 의미합니다.
2. 방법 VK§, (K-요소 검증) - 이전에 DK() 방법의 기능에 의해 결정된 동일한 수준의 K-요소와 고려된 K-요소의 동일성을 확인합니다.
3. 방법 DEO(K 요소의 끝 정의) - K 요소의 끝을 결정합니다. 즉, Kt 요소를 정의할 때 수정된 Kt-1 요소를 찾습니다. 레벨 t-1의 DE() 메소드 함수는 레벨 t의 DK() 메소드 함수에 의해 호출된다.
4. 방법 VE(),(K 요소의 끝 확인) - 고려된 K 요소의 끝이 DE() 메서드의 함수에 의해 이전에 정의된 수정된 K 요소와 일치하는지 확인합니다.
Cmini 클래스는 동일한 메서드를 포함하고 있으며, Cmini 클래스의 메서드는 L 요소에 대해 동작하고 K0 요소를 결정하거나 확인한다는 점에서 CKForLn 클래스의 메서드와 다릅니다.
Cmini 클래스 방법
Cmini 클래스의 메서드는 메서드 함수가 호출되는 순간 L 요소의 현재 번호부터 시작하여 처리된 이미지의 각 윤곽선에 대해 구성된 L 요소의 초기 데이터 시퀀스로 사용합니다.
Cmini 클래스의 DK() 메서드의 함수는 일치할 때까지 각 다음 L 요소의 매개변수를 초기 L 요소의 매개변수와 비교합니다. 매개변수가 일치하지 않으면 DK() 함수는 K0 요소가 완료되었는지 확인하고 종료합니다.
일하다. K0 요소는 길이가 K0 요소의 다른 L 요소와 1만큼 다른 수정된 L 요소로 끝나는 경우 완료된 것으로 간주됩니다(세그먼트 시작에 대한 작업 3.1 - t = 0).
VK() 메서드의 함수는 다음 k0 L 요소의 매개변수가 이전에 DK() 메서드의 함수에 의해 정의된 K0 요소의 L 요소 매개변수와 일치하는지 여부를 확인합니다.
같은 수준. 현재 K0 요소의 매개변수가 이전 요소와 일치하는 경우
정의되면 VK() 함수는 세그먼트 연속의 부호를 생성하고 종료합니다(세그먼트 연속에 대한 작업 3.1 - t > 0).
그렇지 않으면 VK() 함수는 세그먼트 끝의 부호를 생성하고 끝납니다.
DE() 메서드 함수는 현재 Kci 요소의 매개변수를 이전에 DK() 함수로 정의한 K0 요소의 매개변수와 비교하여 현재 K0 요소가 변경되었는지 확인합니다. 다른 매개변수가 같으면 L 요소의 수 k0
이전에 정의된 K0 요소와 비교하여 수정된 K0 요소의
함수 DK()는 1만큼 달라야 합니다(완료를 결정하기 위한 작업 3.2, 3.3).
초기 K0 -세그먼트의 요소 - t = 0). 결과 - 수정된 K0 요소의 매개변수
Cmini 클래스의 VE() 메서드에서 사용됩니다.
VE() 메서드 함수는 현재 K0 요소의 매개변수를 이전에 DE() 함수로 정의한 수정된 K0 요소의 매개변수와 비교하여 다음을 결정합니다.
일치합니까 (세그먼트 연속을위한 작업 3.2, 3.3-t> 0). 결과(일치 또는 불일치의 표시)는 CKForLn 클래스의 VK() 메서드에서 사용됩니다.
CKForLn 클래스의 메서드
이 방법은 가장 낮은 수준에 대해 구성된 K-요소의 매개변수를 초기 데이터로 사용합니다. 즉, Kt 요소의 매개변수를 결정하기 위해 매개변수가 사용됩니다.
이미 구성된 Kt-l -요소.
CKForLn 클래스의 레벨 t의 DK() 메서드의 함수는 ^-요소의 매개변수를 결정할 때 CKForLn 클래스의 레벨 t-1의 VK() 함수를 호출하여 이미 정의된 Kt가 -l 요소 다음에는 매개변수가 동일한 Kt-l 요소가 옵니다. 그렇다면 VK() 함수 호출이 반복됩니다. 이 경우 반복 횟수가 계산됩니다. 즉 매개 변수 kt가 결정됩니다.
그렇지 않으면 레벨 t의 DK() 함수는 레벨 t-1의 DE() 함수를 호출하여 수정된 Kt-l 요소를 결정하고 종료합니다. 작업의 끝에서 CKForLn 클래스의 레벨 t의 DK() 함수는 매개변수를 결정하고 완료되거나 불완전한 Kt 요소의 기호를 생성합니다(현재 최대값이 t인 작업 4.1, 4.2).
CKForLn 클래스의 레벨 t의 VK() 메서드의 함수는 다음 kt Kt -elements의 매개변수가 이전에 정의된 Kt -element의 매개변수와 동일한지 확인합니다.
같은 수준의 DK() 메소드의 기능. 현재 Kt-요소의 매개변수가 다음과 일치하는 경우
DK() 함수에 의해 미리 정의된 Kt -동일한 수준의 요소인 VK() 함수
세그먼트의 연속 표시를 생성하고 작업을 완료합니다.
그렇지 않으면 VK() 함수는 세그먼트 끝의 부호를 생성하고 종료합니다(현재 값 t가 최대값보다 작은 작업 4.1,4.2).
Kt 요소 CKForLn 클래스의 DE0 레벨 t 메소드의 기능은 Kt 요소의 매개변수를 결정할 때 현재 Kt 요소의 매개변수와 이전에 DK() 함수에 의해 정의된 Kt 요소의 매개변수를 비교하여 다음을 결정합니다. 현재 Kt 요소가 변경되었습니다. 다른 파라미터가 같으면 kt-1 값이 1만큼 달라야 합니다. 이 조건이 충족되면 DE() 함수는 변경된 Kt 요소의 부호를 생성하고
종료합니다(t의 현재 최대값에서 작업 4.3, 4.4).
CKForLn 클래스의 t 레벨의 VE() 메소드의 기능은 현재 Kt 요소의 매개변수와 이전에 DE() 함수에 의해 할당된 변경된 Kt 요소의 매개변수를 비교하여 매개변수 값이 일치하는지를 판단한다.
현재 Kt 요소의 파라미터 값이 이전과 일치하는 경우
동일한 수준의 DK() 함수에 의해 정의된 VK() 함수는 매개변수 값이 일치한다는 신호를 생성하고 종료합니다(현재 값이 최대값보다 작은 4.3,4.4 작업).
타이밍 다이어그램(그림 2)은 직선 세그먼트 인식의 예를 사용하여 LINESEGM 프로그램의 작동을 보여줍니다. 그림의 아래 부분은 주 방향과 보조 방향이 같고 길이가 다른 L 요소로 구성된 디지털 라인의 일부를 보여줍니다.
0 단계에서 K0 요소의 매개 변수를 정의하는 Stіnі 클래스의 개체가 생성됩니다.
10 단계에서 K0 요소의 매개변수 결정이 완료되고 이전에 생성된 개체의 기능을 사용하여 K1 요소의 매개변수를 결정하는 CRORGn 클래스의 개체 1이 생성됩니다. 19단계에서 K1 요소의 매개변수 정의가 완료되고 이전에 생성된 개체의 기능을 사용하여 K2 요소의 매개변수를 결정하는 CCROGn 클래스의 개체 2가 생성됩니다. 단계 49에서 K2 요소의 매개변수 결정이 완료되고 이전에 생성된 개체의 기능을 사용하여 K3 요소의 매개변수를 결정하는 CRORGn 클래스의 개체 3이 생성됩니다. 79단계에서,
종료 조건. 프로그램의 작동은 부록에 자세히 설명되어 있습니다.
섹션 0-6에서 두 개의 b 요소가 미완성 K0 요소를 형성합니다. b-는 명백하다.
길이 3의 요소 3-6은 선분을 완성합니다. 길이 1의 요소 b-요소 6-7은 그 연속이 될 수 없기 때문입니다. 따라서 b-요소 6-7은 디지털 라인 세그먼트의 시작입니다.
무화과에. 3은 프로그램 작동 방식의 예를 보여줍니다. 곱슬 화살표의 이진 이미지 윤곽선은 사각형으로 직선 세그먼트로 나뉩니다. 일련의 선 세그먼트인 프로그램의 결과는 디지털 곡선의 호를 강조 표시하는 데 사용되었습니다. 큰 사각형은 디지털 곡선 호의 경계를 나타냅니다.
프로그램의 작동은 많은 수의 예제(2000개 이상)에서 테스트되었으며 하프톤 이미지의 구조 분석 연구에 사용됩니다.
5. 선분 인식 프로그램 작업
그림의 예에서 iEBESM 프로그램의 작업을 고려해 봅시다. 4. 그림의 아래 부분은 주 방향과 보조 방향이 같고 길이가 다른 b-요소로 구성된 디지털 라인의 일부를 보여줍니다. 섹션 0-6에서 두 개의 b 요소가 불완전한 K0-를 형성합니다.
쌀. 3. 윤곽의 구조 분석을 위한 프로그램 작업의 예 - 디지털 직선 세그먼트로 윤곽 분할
요소. 분명히, 길이 3의 b-요소 3-6은 선분을 완성합니다. 길이 1의 b-요소 6-7은 그것의 연속이 될 수 없기 때문입니다. 따라서 b-요소 6-7은 디지털 라인 세그먼트의 시작입니다.
직선의 다음 세그먼트를 결정하는 프로그램 작업은 제로 레벨의 OK() 함수에 의해 시작되며, 이는 b-요소로 구성된 완성된 K0 -요소 6-10을 결정합니다.
길이 1,1,2; k0=2. 이 K0 요소는 K1 요소의 시작 요소입니다. 프로그램은 첫 번째 수준의 개체를 형성하고 이 개체의 OK() 함수로 제어를 전송합니다. 레벨 1의 OK() 함수는 레벨 0의 VKQ 함수를 호출합니다. VKQ 함수는 K0-엘리먼트 6-10의 b-엘리먼트의 파라미터를 후속 b-엘리먼트와 비교하여 K0-엘리먼트 10-14의 존재를 확인하고,
K0 - 요소 6-10과 동일합니다. 계속해서 VKQ 함수는 다음 b 요소가 동일한 K0 요소를 형성하지 않음을 감지하고 종료하고 OK() 수준 1 함수로 제어를 전송합니다. 수준 1 OK() 함수는 수준 0 OE() 함수를 호출합니다. b-요소 6-7, 길이 1,1,1,2의 b-요소로 구성된 수정된 K0 요소 14-19의 존재를 결정합니다. k0=3, 종료하고 수준 1의 OK() 함수로 제어를 전송합니다. 이 함수는 두 개의 K0 -
요소 1,1,2, (k1=2) 및 변경된 요소 1,1,1,2(k0=3). 프로그램은 두 번째 수준의 개체를 형성하고 이 개체의 OK() 함수로 제어를 전송합니다. 레벨 2 OK() 함수는 레벨 1 VKQ 함수를 호출하고 레벨 0 VKQ 함수를 호출합니다. VKQ 함수는 K0 요소 6-10의 b-요소를 다음 b와 비교합니다.
요소를 확인하고 K0 요소 6-10과 동일한, 즉 K1 요소 6-19에 이러한 K0 요소와 동일한 개수의 K0 요소 19-23, 23-27이 포함되어 있음을 확인합니다. 다음으로 레벨 0의 VKQ 함수는 레벨 1의 VKQ 함수 세그먼트를 계속한다는 부호로 제어를 반환합니다. VKQ 함수는 레벨 0의 함수 VE0를 호출하여 변경된 K0-
K0 요소 14-19와 동일한 요소 27-32. 따라서 K1-요소 19-32는 다음과 같이 정의됩니다.
K1 요소 6-19와 동일합니다. 또한 레벨 1 VKQ 함수는 K1 요소 6-19와 동일한 다음 K1 요소를 결정하지 않습니다. 레벨 0 함수 VE0는 b 요소부터 시작하여 K1 요소 6-19와 동일한 수정된 K1 요소를 결정하지 않기 때문입니다. 40-41, 수준 2의 OK() 함수 제어를 반환합니다. 수준 2의 OK() 함수는 수준 1의 OE() 함수를 호출하며, 수정된 K1 요소 32-49의 존재를 결정합니다. K0 요소 32-36, 36-40,
40-44, 44-49. 다음으로, K2 요소(6-49)가 결정되고, 레벨 3 객체가 형성되고, 변형된 K2 요소(49-79)가 결정된다. 이 두 개의 K2 요소는 K3 요소 6-79를 형성합니다. 이것으로 세그먼트 구성이 완료되는데, 다음 b-요소 79-81 및 81-83은 K0 요소를 형성하지 않으므로,
K0 요소 6-10과 동일하며 레벨 0 VKQ 기능은 연속 플래그를 생성하지 않습니다.
분절. b-요소 시퀀스에서 디지털 직선 6-79의 세그먼트가 선택됩니다. 프로그램은 b-요소 80-82부터 시작하여 다음 세그먼트의 정의를 시작합니다.
비. 결론
1. 이미지 윤곽에서 라인 세그먼트를 선택하기 위한 새로운 알고리즘과 알고리즘의 중요한 소프트웨어 구현이 제안되어 이미지 윤곽을 라인 세그먼트 시퀀스로 인식하는 문제에 대한 정확한 솔루션을 얻을 수 있습니다.
2. 이미지 윤곽선에서 선분을 선택하는 알고리즘의 소프트웨어 구현은 최신 객체 지향 프로그래밍 도구를 사용하여 이루어지므로 처리된 이미지의 크기에 명시적인 제한을 두지 않고 리소스 사용을 최대화할 수 있습니다. 사용하는 컴퓨터.
3. 제안한 알고리즘과 소프트웨어 구현을 기반으로 이론적인 해를 구하고 디지털 곡선의 호를 인식하고 디지털 선의 세그먼트와 디지털 곡선의 호에서 이진 영상의 윤곽을 분할하는 실험을 수행하였다.
서지
1. Kovalevsky V.A. 경제적인 이미지 인코딩에 대한 디지털 스트레이트 세그먼트의 응용, 제7회 국제 워크샵 진행, DGCI"97, Montpellier. - 프랑스, 1997. - 12월 3-5. - P. 51-62.
2. Kalmykov V.G. 이진 이미지의 윤곽에서 디지털 라인의 세그먼트를 설명하고 인식하는 구조적 방법 // Piece Intellect. - 2002. - 4호. - C. 450-457.
3. Kalmykov V.G., Vishnevsky V.V. 이진 이미지의 객체 윤곽 분석 // 수학적 기계 및 시스템. - 1997. - 2호. - S. 68 - 71.
4. 칼미코프 V.G. 디지털 곡선의 호 - 지정 및 정체 // 신호 처리 및 이미지 인식 및 이미지 인식. All-Ukrainian International Conference의 절차. - 키이우. - 2004. - 11 - 15 조브텐.