Reconfigurable mesh algorithms for image shrinking, expanding, clustering, and template matching

John Jenq, Sartaj Sahni

Research output: Chapter in Book/Report/Conference proceedingConference contribution

37 Citations (Scopus)

Abstract

Parallel reconfigurable mesh algorithms are developed for the following image processing problems: shrinking, expanding, clustering, and template matching. Our N×N reconfigurable mesh algorithm for the q-step shrinking and expansion of a binary image takes 0 (1) time. One pass of the clustering algorithm for N patterns and K centers can be done in O(MK + KlogN), O(KlogNM), and O (M + logNMK) time using N, NM, and NMK processors, respectively. For template matching using an M×M template and an N×N image, our algorithms run in O (M2) time when N2 processors ate available and in O (M) time when N2M2 processors are available.

Original languageEnglish
Title of host publicationProceedings - 5th International Parallel Processing Symposium, IPPS 1991
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages208-215
Number of pages8
ISBN (Electronic)0818691670, 9780818691676
DOIs
StatePublished - 1 Jan 1991
Event5th International Parallel Processing Symposium, IPPS 1991 - Anaheim, United States
Duration: 30 Apr 19912 May 1991

Publication series

NameProceedings - 5th International Parallel Processing Symposium, IPPS 1991

Conference

Conference5th International Parallel Processing Symposium, IPPS 1991
CountryUnited States
CityAnaheim
Period30/04/912/05/91

Fingerprint

Reconfigurable Mesh
Template matching
Template Matching
Shrinking
Clustering
Binary images
Clustering algorithms
Binary Image
Image processing
Clustering Algorithm
Template
Image Processing

Keywords

  • Clustering
  • Expanding
  • Image processing
  • Parallel algorithms
  • Reconfigurable mesh computer
  • Shrinking
  • Template matching

Cite this

Jenq, J., & Sahni, S. (1991). Reconfigurable mesh algorithms for image shrinking, expanding, clustering, and template matching. In Proceedings - 5th International Parallel Processing Symposium, IPPS 1991 (pp. 208-215). [153780] (Proceedings - 5th International Parallel Processing Symposium, IPPS 1991). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPPS.1991.153780
Jenq, John ; Sahni, Sartaj. / Reconfigurable mesh algorithms for image shrinking, expanding, clustering, and template matching. Proceedings - 5th International Parallel Processing Symposium, IPPS 1991. Institute of Electrical and Electronics Engineers Inc., 1991. pp. 208-215 (Proceedings - 5th International Parallel Processing Symposium, IPPS 1991).
@inproceedings{e9259772d771448b9783f8c417a773f8,
title = "Reconfigurable mesh algorithms for image shrinking, expanding, clustering, and template matching",
abstract = "Parallel reconfigurable mesh algorithms are developed for the following image processing problems: shrinking, expanding, clustering, and template matching. Our N×N reconfigurable mesh algorithm for the q-step shrinking and expansion of a binary image takes 0 (1) time. One pass of the clustering algorithm for N patterns and K centers can be done in O(MK + KlogN), O(KlogNM), and O (M + logNMK) time using N, NM, and NMK processors, respectively. For template matching using an M×M template and an N×N image, our algorithms run in O (M2) time when N2 processors ate available and in O (M) time when N2M2 processors are available.",
keywords = "Clustering, Expanding, Image processing, Parallel algorithms, Reconfigurable mesh computer, Shrinking, Template matching",
author = "John Jenq and Sartaj Sahni",
year = "1991",
month = "1",
day = "1",
doi = "10.1109/IPPS.1991.153780",
language = "English",
series = "Proceedings - 5th International Parallel Processing Symposium, IPPS 1991",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "208--215",
booktitle = "Proceedings - 5th International Parallel Processing Symposium, IPPS 1991",

}

Jenq, J & Sahni, S 1991, Reconfigurable mesh algorithms for image shrinking, expanding, clustering, and template matching. in Proceedings - 5th International Parallel Processing Symposium, IPPS 1991., 153780, Proceedings - 5th International Parallel Processing Symposium, IPPS 1991, Institute of Electrical and Electronics Engineers Inc., pp. 208-215, 5th International Parallel Processing Symposium, IPPS 1991, Anaheim, United States, 30/04/91. https://doi.org/10.1109/IPPS.1991.153780

Reconfigurable mesh algorithms for image shrinking, expanding, clustering, and template matching. / Jenq, John; Sahni, Sartaj.

Proceedings - 5th International Parallel Processing Symposium, IPPS 1991. Institute of Electrical and Electronics Engineers Inc., 1991. p. 208-215 153780 (Proceedings - 5th International Parallel Processing Symposium, IPPS 1991).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Reconfigurable mesh algorithms for image shrinking, expanding, clustering, and template matching

AU - Jenq, John

AU - Sahni, Sartaj

PY - 1991/1/1

Y1 - 1991/1/1

N2 - Parallel reconfigurable mesh algorithms are developed for the following image processing problems: shrinking, expanding, clustering, and template matching. Our N×N reconfigurable mesh algorithm for the q-step shrinking and expansion of a binary image takes 0 (1) time. One pass of the clustering algorithm for N patterns and K centers can be done in O(MK + KlogN), O(KlogNM), and O (M + logNMK) time using N, NM, and NMK processors, respectively. For template matching using an M×M template and an N×N image, our algorithms run in O (M2) time when N2 processors ate available and in O (M) time when N2M2 processors are available.

AB - Parallel reconfigurable mesh algorithms are developed for the following image processing problems: shrinking, expanding, clustering, and template matching. Our N×N reconfigurable mesh algorithm for the q-step shrinking and expansion of a binary image takes 0 (1) time. One pass of the clustering algorithm for N patterns and K centers can be done in O(MK + KlogN), O(KlogNM), and O (M + logNMK) time using N, NM, and NMK processors, respectively. For template matching using an M×M template and an N×N image, our algorithms run in O (M2) time when N2 processors ate available and in O (M) time when N2M2 processors are available.

KW - Clustering

KW - Expanding

KW - Image processing

KW - Parallel algorithms

KW - Reconfigurable mesh computer

KW - Shrinking

KW - Template matching

UR - http://www.scopus.com/inward/record.url?scp=0002395895&partnerID=8YFLogxK

U2 - 10.1109/IPPS.1991.153780

DO - 10.1109/IPPS.1991.153780

M3 - Conference contribution

AN - SCOPUS:0002395895

T3 - Proceedings - 5th International Parallel Processing Symposium, IPPS 1991

SP - 208

EP - 215

BT - Proceedings - 5th International Parallel Processing Symposium, IPPS 1991

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Jenq J, Sahni S. Reconfigurable mesh algorithms for image shrinking, expanding, clustering, and template matching. In Proceedings - 5th International Parallel Processing Symposium, IPPS 1991. Institute of Electrical and Electronics Engineers Inc. 1991. p. 208-215. 153780. (Proceedings - 5th International Parallel Processing Symposium, IPPS 1991). https://doi.org/10.1109/IPPS.1991.153780